还是线性dp，有点感觉了，另外这个问题也可以用滚动数组
/* 依然是先按照阶段i划分， dp[i][j][k]表示完成第i个请求时，两个员工分别在j位置和k位置的费用（还有一个员工一定在位置p） dp[i][j][k]=min(dp[i][j][k],dp[i-1][j][k]+cost[pre][p]);处理完上一个请求的员工处理下一个请求，其余两个不懂 dp[i][j][pre]=min(dp[i][j][pre],dp[i-1][j][k]+cost[k][p]);处理完上一个请求的员工不动，余下两个中的一个处理下一个请求 dp[i][k][pre]=min(dp[i][k][pre],dp[i-1][j][k]+cost[j][p]);处理完上一个请求的员工不动，余下两个中的一个处理下一个请求 */ #include<iostream> #include<cstring> #include<cstdio> #include<algorithm> using namespace std; int n,l,c[201][201],list[1001],dp[2][201][201]; int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d%d",&l,&n); for(int i=1;i<=l;i++) for(int j=1;j<=l;j++) scanf("%d",&c[i][j]); for(int i=1;i<=n;i++) scanf("%d",&list[i]); memset(dp,0x7f,sizeof dp); int las=1,now=0,ans=0x7fffffff,pre,p; dp[0][1][2]=c[3][list[1]]; dp[0][1][3]=c[2][list[1]]; dp[0][2][3]=c[1][list[1]]; for(int i=2;i<=n;i++){//依次处理每个订单 las^=1,now^=1;pre=list[i-1],p=list[i];//滚动数组翻转一下 memset(dp[now],0x7f,sizeof dp[now]);//把原来的数据清空 for(int i=1;i<=l;i++) for(int j=1;j<=l;j++){ if(i==j||i==pre||j==pre) continue; dp[now][i][j]=dp[now][j][i]=min(dp[now][i][j],dp[las][i][j]+c[pre][p]);//第一种情况 dp[now][i][pre]=dp[now][pre][i]=min(dp[now][i][pre],dp[las][i][j]+c[j][p]); dp[now][j][pre]=dp[now][pre][j]=min(dp[now][j][pre],dp[las][i][j]+c[i][p]); } } for(int i=1;i<=l;i++) for(int j=1;j<=l;j++) if(i!=j && i!=list[n] && j!=list[n])ans=min(ans,dp[now][i][j]); printf("%d ",ans); } }