动态规划 - SPOJ 服务中的 DP 状态

Question

我在 SPOJ 上的服务问题中遇到了问题。我试图解决它，并提出了以下DP状态[posofA][posofB][posofC][NextToMove]。但从约束来看，我认为它会给MLE。尝试了一天后，我用谷歌搜索了一下，找到了关于问题对称性的博客。尽管我尽了最大的努力，但我无法理解它。有人可以帮忙，抽出时间帮助我吗？谢谢。

Answer 1

观察你可以

去掉posOfC，并始终用最后一个请求的位置来表示posOfC。当您处理请求时，您可以轻松获得之前的位置。现在您拥有 3 个合作伙伴的所有职位。将其中一个发送到新请求的位置，检查它们是否都位于不同的位置。

int f(int pos,int a,int b)
{
        if(pos == req.sz)
                return 0;
        // last position
        int c = req[pos-1];
        // current position we are sending one of them
        int to = req[pos];
        if( dp[pos][a][b] != -1)
                return dp[pos][a][b];
        int ans = inf;
        // a goes to current request position
        if(b != c && b != to && c != to)
                ans = min(ans,f(pos+1,b,c) + cost[a][to]);
        // b goes to current request position
        if(a != c && a != to && c != to)
                ans = min(ans,f(pos+1,a,c) + cost[b][to]);
        // c goes to current request position
        if(a != b && a != to && b != to)
                ans = min(ans , f(pos+1,a,b) + cost[c][to]);
        return dp[pos][a][b] = ans;
}

要求的前 3 个元素将是 1,2,3 。通过致电f(3,1,2)获得答案。