线型动态规划的好题……
分析题意，不难设计出状态：f[i][x][y][z]表示完成第i个任务后，三个人分别在x,y,z位置时的花费。但是这样的状态时间与空间都无法承受，不可行。
再次考虑：当完成第i个任务后，其中一人必定在p[i]上，因此状态可以减少一维：f[i][x][y]表示完成第i个任务后，另外两个人（除了这一步移动的到p[i]的那个人）分别在x,y位置时的花费。
考虑状态转移：若当前位于状态f[i][x][y]，当前要处理第i+1个任务，要去往p[i+1]位置。设当前位于p[i]的那个人为z。c数组表示花费（见题目描述）。
1、如果让x去p[i+1]（y,z不在那里）,则f[i+1][y][z]=min(f[i+1][y][z],f[i][x][y]+c[x][p[i+1]]).
2、如果让y去p[i+1]（x,z不在那里）,则f[i+1][x][z]=min(f[i+1][x][z],f[i][x][y]+c[y][p[i+1]]).
3、如果让z去p[i+1]（x,y不在那里）,则f[i+1][x][y]=min(f[i+1][x][y],f[i][x][y]+c[z][p[i+1]]).
另外，我们发现第i个任务的状态只能从第i-1个任务的状态转移过来，也就是说我们可以用滚动数组优化空间，只存i和i-1，每次计算都覆盖掉原来的状态。
这样我们就不难得出正解。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 using namespace std; 5 int n,m; 6 int c[210][210],ans,p[1010]; 7 int f[2][210][210]; 8 int main() { 9 scanf("%d%d",&m,&n); 10 for(int i=1;i<=m;i++) 11 for(int j=1;j<=m;j++) 12 scanf("%d",&c[i][j]); 13 for(int i=1;i<=n;i++) scanf("%d",&p[i]); 14 p[0]=3; 15 memset(f,0x3f,sizeof(f)); 16 f[0][1][2]=0; 17 for(int i=1;i<=n;i++) { 18 for(int x=1;x<=m;x++) { 19 for(int y=1;y<=m;y++) 20 if(f[i-1&1][x][y]!=0x3f3f3f3f) { 21 int z=p[i-1]; 22 if(x!=p[i]&&y!=p[i]) f[i&1][x][y]=min(f[i&1][x][y],f[i-1&1][x][y]+c[z][p[i]]); 23 if(x!=p[i]&&z!=p[i]) f[i&1][x][z]=min(f[i&1][x][z],f[i-1&1][x][y]+c[y][p[i]]); 24 if(y!=p[i]&&z!=p[i]) f[i&1][y][z]=min(f[i&1][y][z],f[i-1&1][x][y]+c[x][p[i]]); 25 f[i-1&1][x][y]=0x3f3f3f3f; 26 } 27 } 28 } 29 ans=1<<30; 30 for(int i=1;i<=m;i++) 31 for(int j=1;j<=m;j++) 32 ans=min(ans,f[n&1][i][j]); 33 printf("%d\n",ans); 34 return 0; 35 }
原文：https://www.cnblogs.com/shl-blog/p/10660405.html
