有一\(1\times L\)的网格，3个人初始在1,2,3,给出从每个位置i移到另一个位置j的费用\(c[i][j]\)，并且保证两个人不在同一位置，再给出n个请求，第i个请求记做\(p_i\)，要求有一个人到达位置\(p_i\)，问按先后顺序完成这些请求的最小费用，\(3<=L<=200, 1<=N<=1000\)。
解
显然要表现出这是第几个请求，且要知道3个人的位置才能转移，故设\(f[i][j][k][l]\)表示第i个请求，位置分别在j，k，l的最小费用，但是注意到\(p[i]\)已经表示了一个人的费用，故只要设\(f[i][j][k]\)表示第i个请求，有2个人在位置j,k的最小费用，于是我们有
\[f[i+1][j][k]=\max(f[i+1][j][k],f[i][j][k]+c[p[i]][p[i+1]])(p[i+1]!=j,k)\]
\[f[i+1][j][p[i]]=\max(f[i+1][j][p[i]],f[i][j][k]+c[k][p[i+1]])(p[i+1]!=p[i],j)\]
\[f[i+1][k][p[i]]=\max(f[i+1][j][p[i]],f[i][j][k]+c[j][p[i+1]])(p[i+1]!=p[i],k)\]
边界:\(f[0][1][2]=0,p[0]=3\),其余无限大
答案：\(\min_{i,j=1}^L f[n][i][j](i\neq j)\)
参考代码：
阶段实现
#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
#define intmax 0x7fffffff
using namespace std;
int c[201][201],dp[1001][201][201],
p[1001];
il void read(int&);
template<class free>
il free Min(free,free);
int main(){
int l,n;
read(l),read(n),memset(dp,66,sizeof(dp));
for(int i(1),j;i<=l;++i)
for(j=1;j<=l;++j)read(c[i][j]);
for(int i(1);i<=n;++i)read(p[i]);
p[0]=3,dp[0][1][2]=0;
for(int i(0),j,k;i<n;++i)
for(j=1;j<=l;++j)
for(k=1;k<=l;++k){
if(j==k||j==p[i]||k==p[i])continue;
if(p[i+1]!=j&&p[i+1]!=k)dp[i+1][j][k]=Min(dp[i+1][j][k],dp[i][j][k]+c[p[i]][p[i+1]]);
if(p[i+1]!=j&&p[i+1]!=p[i])dp[i+1][j][p[i]]=Min(dp[i+1][j][p[i]],dp[i][j][k]+c[k][p[i+1]]);
if(p[i+1]!=k&&p[i+1]!=p[i])dp[i+1][k][p[i]]=Min(dp[i+1][k][p[i]],dp[i][j][k]+c[j][p[i+1]]);
}
int ans(intmax);
for(int i(1),j;i<=l;++i)
for(j=1;j<=l;++j)ans=Min(ans,dp[n][i][j]);
printf("%d",ans);
return 0;
}
template<class free>
il free Min(free a,free b){
return a<b?a:b;
}
il void read(int &x){
x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}dfs实现（超了时，恳求优化）
#include <iostream>
#include <cstdio>
#include <cstring>
#define il inline
#define ri register
#define intmax 0x7fffffff
using namespace std;
int w[201][201],p[201],
dp[1001][201][201],n;
void search(int,int,int);
il void read(int&);
int main(){
int l;read(l),read(n);
for(int i(1),j;i<=l;++i)
for(j=1;j<=l;++j)read(w[i][j]);
for(int i(1);i<=n;++i)read(p[i]);
memset(dp,66,sizeof(dp));
dp[0][1][2]=0,p[0]=3,search(0,1,2);
int ans(intmax);
for(int i(1),j;i<=l;++i)
for(j=1;j<=l;++j)
ans=ans>dp[n][i][j]?dp[n][i][j]:ans;
printf("%d",ans);
return 0;
}
void search(int a,int b,int c){
if(a==n)return;int opt;
if(p[a+1]!=b&&p[a+1]!=c)
if((opt=dp[a][b][c]+w[p[a]][p[a+1]])<dp[a+1][b][c])
dp[a+1][b][c]=opt,search(a+1,b,c);
if(p[a+1]!=p[a]){
if(p[a+1]!=b)
if((opt=dp[a][b][c]+w[c][p[a+1]])<dp[a+1][b][p[a]])
dp[a+1][b][p[a]]=opt,search(a+1,b,p[a]);
if(p[a+1]!=c)
if((opt=dp[a][b][c]+w[b][p[a+1]])<dp[a+1][c][p[a]])
dp[a+1][c][p[a]]=opt,search(a+1,c,p[a]);
}
}
il void read(int &x){
x&=0;ri char c;while(c=getchar(),c<'0'||c>'9');
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}