Sol
首先状态是已经完成的请求数量
这题只有三个员工跑来跑去，只有三个....
一般像这种人数特别少的DP题就会把它们都放到状态里去
于是：f[i][x][y][z]表示现在已经完成了i个请求，一个员工在x,一个员工在y,一个员工在z的最小花费
转移：
f[i+1][pi+1][y][z]=min(f[i+!][pi+1][y][z],f[i][x][y][z]+c(x,pi+1))
f[i+1][x][pi+1][z]=min(f[i+1][x][pi+1][z],f[i][x][y][z]+c(y,pi+1))
f[i+1][x][y][pi+1]=min(f[i+1][x][y][pi+1],f[i][x][y][z]+c(z,pi+1));
注意到，当第i个请求完成时，一定有一个员工位于pi,只需要描述另外两个员工的位置即可以描述整个状态
所以：f[i][x][y]表示现在已经完成了i个请求，一个员工在pi,另外两个员工在x,y的最小花费
转移：
f[i+1][pi][y]=min(f[i+1][pi][y],f[i][x][y]+c(x,pi+1))
f[i+1][x][pi]=min(f[i+1][x][pi],f[i][x][y]+c(y,pi+1))
f[i+1][x][y]=min(f[i+1][x][y],f[i][x][y]+c(pi,pi+1))
最后，其实这里还可以用滚动数组优化
over!
Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #define Rg register 5 #define il inline 6 #define db double 7 #define ll long long 8 #define inf 2100000000 9 #define mem(a,b) memset(a,b,sizeof(a)); 10 #define go(i,a,b) for(Rg int i=a;i<=b;i++) 11 #define yes(i,a,b) for(Rg int i=a;i>=b;i--) 12 using namespace std; 13 il int read() 14 { 15 int x=0,y=1;char c=getchar(); 16 while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();} 17 while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+c-'0';c=getchar();} 18 return x*y; 19 } 20 int T,l,n,ans=inf,p[1001],c[201][201],f[1001][201][201]; 21 int main() 22 { 23 T=read(); 24 while(T--) 25 { 26 l=read(),n=read();mem(f,0x3f);ans=inf; 27 go(i,1,l)go(j,1,l)c[i][j]=read(); 28 go(i,1,n)p[i]=read(); 29 f[0][1][2]=0;p[0]=3; 30 go(i,0,n-1) 31 go(x,1,l) 32 go(y,1,l) 33 { 34 if(x==y || x==p[i] || y==p[i])continue; 35 if(y!=p[i+1] && p[i]!=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]]); 36 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]]); 37 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]]); 38 } 39 go(x,1,l)go(y,1,l)ans=min(ans,f[n][x][y]); 40 printf("%d ",ans); 41 } 42 return 0; 43 }