题目链接：https://vjudge.net/problem/SPOJ-SERVICE
好题。首先可以考虑设计一个思维状态f[i][x][y][z]表示完成第i个，三个人分别位于x,y,z位置的最小费用，但是这样dp的时间复杂度是O（nL^3）的。注意到完成第i个，一定有一个人的位置在Pi。于是可以只用剩下两人的位置来定义状态：f[i][j][k]表示完成第i个，除了位置在Pi的人以外，其他两人的位置在j和k的最小费用，从阶段i-1到阶段i的状态间，3个人都可以移动到Pi。有如下转移方程：
f[i][j][k]=min(f[i][j][k],f[i-1][j][k]+c(Pi-1,Pi))，阶段i-1中，j和k不动，位置Pi-1的人移到Pi
f[i][Pi-1][k]=min(f[i][Pi-1][k],f[i-1][j][k]+c(j,Pi))，阶段i-1中，在Pi-1位置的人不动，位置j的人移到Pi
f[i][j][Pi-1]=min(f[i][j][Pi-1],f[i-1][j][k]+c(k,Pi))，阶段i-1中，在Pi-1位置的人不动，位置k的人移到Pi
注意状态的合法性，因为不能多个人在同一个位置（见下面代码写状态转移时的很多if）。另外原题空间给的多，不用滚动数组，但是空间如果限制到比如128mb就需要了，但是我滚到连样例都没过去......所以先给出一个不用滚动数组的代码
#include<bits/stdc++.h>
using namespace std;
int c[210][210],p[1010],f[1010][210][210];
int t,n,l,i,j,k;
int main(){
scanf("%d",&t);
while (t--){
scanf("%d%d",&l,&n);
for (i=1;i<=l;i++)
for (j=1;j<=l;j++) scanf("%d",&c[i][j]);
for (i=1;i<=n;i++) scanf("%d",&p[i]);
memset(f,0x3f,sizeof(f));
f[0][1][2]=0; p[0]=3;
for (i=1;i<=n;i++)
for (j=1;j<=l;j++)
for (k=1;k<=l;k++){
if (j==p[i-1]||k==p[i-1]||j==k) continue; //*
if (j!=p[i]&&k!=p[i])
f[i][j][k]=min(f[i][j][k],f[i-1][j][k]+c[p[i-1]][p[i]]);
if (k!=p[i]&&p[i-1]!=p[i])
f[i][p[i-1]][k]=min(f[i][p[i-1]][k],f[i-1][j][k]+c[j][p[i]]);
if (j!=p[i]&&p[i-1]!=p[i])
f[i][j][p[i-1]]=min(f[i][j][p[i-1]],f[i-1][j][k]+c[k][p[i]]);
}
int ans=1e9;
for (i=1;i<=l;i++)
for (j=1;j<=l;j++) ans=min(ans,f[n][i][j]);
printf("%d\n",ans);
}
return 0;
}
spoj703 Mobile Service---线性dp+状态简化
原文：https://www.cnblogs.com/edmunds/p/13583032.html