题目传送门 【题目大意】 有L个位置(编号为1～L)和N个要求，初始状态三个服务员分别在1,2,3号位置，每个要求给出一个位置p[i]，需要一个服务员到这个位置去，已知从位置i到位置j的费
题目传送门
【题目大意】
有L个位置(编号为1～L)和N个要求，初始状态三个服务员分别在1,2,3号位置，每个要求给出一个位置p[i]，需要一个服务员到这个位置去，已知从位置i到位置j的费用为c[i][j]，求最小费用。
【思路分析】
我们用f[i][x][y][z]表示完成了前i个要求，三个服务员分别在x，y，z位置的最小费用。然后我们发现，其中一个服务员必定是在第i个要求的位置的，即z=p[i]，那么有一维数组可以去掉。
接下来看一下转移方程，对于第i+1个要求有三种情况，即让p[i]，x，y位置的服务员的其中一个去到位置p[i+1]，由此可得：
$if(x!=p[i+1]且y!=p[i+1]) f[i+1][x][y]=min(f[i+1][x][y],f[i][x][y]+c[p[i]][p[i+1]])$
$if(p[i]!=p[i+1]且y!=p[i+1]) f[i+1][p[i]][y]=min(f[i+1][p[i]][y],f[i][x][y]+c[x][p[i+1]])$
$if(x!=p[i+1]且p[i]!=p[i+1]) f[i+1][x][p[i]]=min(f[i+1][x][p[i]],f[i][x][y]+c[y][p[i+1]])$
通过观察转移方程我们发现，每一个状态只与其前一个状态有关，所以可以用滚动数组防止爆空间，这一点详见代码。
【代码实现】
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #define rg register 5 #define go(i,a,b) for(rg int i=a;i<=b;i++) 6 using namespace std; 7 int T,l,n,c[202][202],p[1002]; 8 int f[2][202][202]; 9 int ans,a; 10 const int maxn=1e9+7; 11 int main(){ 12 scanf("%d",&T); 13 int x,y; 14 while(T--){ 15 ans=1<<30; 16 scanf("%d%d",&l,&n); 17 go(i,1,l) go(j,1,l) scanf("%d",&c[i][j]); 18 go(i,1,n) scanf("%d",&p[i]); 19 memset(f,0x3f,sizeof(f)); 20 f[0][1][2]=0;p[0]=3; 21 go(k,0,n-1){ 22 a=a^1;//通过异或实现滚动数组 23 memset(f[a],0x3f,sizeof(f[a]));//记得更新初始值 24 x=p[k],y=p[k+1]; 25 go(i,1,l) go(j,1,l){ 26 if(i==j) continue; 27 if(i!=y&&j!=y) f[a][i][j]=min(f[a][i][j],f[a^1][i][j]+c[x][y]); 28 if(x!=y&&j!=y) f[a][x][j]=min(f[a][x][j],f[a^1][i][j]+c[i][y]); 29 if(i!=y&&x!=y) f[a][i][x]=min(f[a][i][x],f[a^1][i][j]+c[j][y]); 30 } 31 } 32 go(i,1,l) go(j,1,l) 33 if(i!=j&&i!=p[n]&&j!=p[n]) 34 ans=min(ans,f[a][i][j]); 35 printf("%d\n",ans); 36 } 37 return 0; 38 }代码戳这里