题目描述：
解析：
这道题我想复杂了，一开始我是这样想的：设dp[i][j]表示按顺序满足到第i个请求时，最初在j号点的人到达第i个请求的位置的情况下的最小花费，state[i][j]表示按顺序满足到第i个请求时，最初在j号点的人到达第i个请求的位置的情况下的各个人的位置状态，状态转移方程就为dp[i][j]=dp[i-1][k]+g[a][requested_loc[i]]，然后就wa了。。。10个过了2.
之后我就一直用这个方法来想，始终过不了，后面不得不看题解。
看完题解后我才发现我一直有个思维误区，那就是必须把原先在1，2，3号点的位置改变要具体表示出来，而且是精确到顺序，正因为这个我一直没有想出正确解法，但其实大可不必如此，题目是求最小值，又不是求到达终点后原先在1，2，3号点各点的精确位置，没必要精确表示原先在1，2，3号点的位置信息，只需大致表示出来就行。
这道题的正确解法是：设f[i][x][y]表示已经处理完前i个请求，且三个服务员分别在p[i], x, y的所有方案的集合，f[i][x][y]的值是集合中所有方案的花费的最小值，那么动态转移方程就为：
位于p[i]的服务员出发前往p[i + 1]，此时状态变成f[i + 1][x][y] = f[i][x][y] + w[p[i]][p[i + 1]];
位于x的服务员出发前往p[i + 1]，此时状态变成f[i + 1][p[i]][y] = f[i][x][y] + w[x][p[i + 1]];
位于y的服务员出发前往p[i + 1]，此时状态变成f[i + 1][x][p[i]] = f[i][x][y] + w[y][p[i + 1]];最终答案从f[m][1…n][1…n]取最小值即可。
错误代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1010,L=210;
int dp[N][5],state[N][5];//dp[i][j]表示按顺序满足到第i个请求时，最初在j号点的人到达第i个请求的位置的情况下的最小花费
//state[i][j]表示按顺序满足到第i个请求时，最初在j号点的人到达第i个请求的位置的情况下的各个人的位置状态,
//比如最初在1号点、2号点和3号点的人此时分别在4，5，6号点，那么4*200*200+5*200+6=161006，即state[i][j]=161006。
int g[L][L]; //存图
int requested_loc[N];
int n,l;
int main()
{
scanf("%d%d",&l,&n);
for(int i=1;i<=l;i++)
{
for(int j=1;j<=l;j++)
scanf("%d",&g[i][j]);
}
for(int i=1;i<=n;i++) scanf("%d",&requested_loc[i]);
memset(dp,0x3f,sizeof(dp));
if(requested_loc[1]!=2&&requested_loc[1]!=3)
{
dp[1][1]=g[1][requested_loc[1]];
state[1][1]=201*201*requested_loc[1]+201*2+3;
}
if(requested_loc[1]!=1&&requested_loc[1]!=3)
{
dp[1][2]=g[2][requested_loc[1]];
state[1][2]=201*201*1+201*requested_loc[1]+3;
}
if(requested_loc[1]!=1&&requested_loc[1]!=2)
{
dp[1][3]=g[3][requested_loc[1]];
state[1][3]=201*201*1+201*2+requested_loc[1];
}
/*
for(int j=1;j<=3;j++)
{
int temp=state[1][j];
int a=temp/40000,b=temp%40000/200,c=temp%40000%200;
printf("各点位置：%d %d %d dp[1][%d]的值为：%d\n",a,b,c,j,dp[1][j]);
}*/
for(int i=2;i<=n;i++)
{
for(int j=1;j<=3;j++)
{
for(int k=1;k<=3;k++)
{
int temp=state[i-1][k];
int a=temp/40401,b=temp%40401/201,c=temp%40401%201;
//cout<<a<<" "<<b<<" "<<c<<endl;
if(j==1)
{
if(requested_loc[i]!=b&&requested_loc[i]!=c)
{
if(dp[i][j]>dp[i-1][k]+g[a][requested_loc[i]])
{
dp[i][j]=dp[i-1][k]+g[a][requested_loc[i]];
state[i][j]=201*201*requested_loc[i]+201*b+c;
}
}
}
else if(j==2)
{
if(requested_loc[i]!=a&&requested_loc[i]!=c)
{
if(dp[i][j]>dp[i-1][k]+g[b][requested_loc[i]])
{
dp[i][j]=dp[i-1][k]+g[b][requested_loc[i]];
state[i][j]=201*201*a+201*requested_loc[i]+c;
}
}
}
else {
if(requested_loc[i]!=a&&requested_loc[i]!=b)
{
if(dp[i][j]>dp[i-1][k]+g[c][requested_loc[i]])
{
dp[i][j]=dp[i-1][k]+g[c][requested_loc[i]];
state[i][j]=201*201*a+201*b+requested_loc[i];
}
}
}
}
/*
int temp=state[i][j];
int a=temp/40000,b=temp%40000/200,c=temp%40000%200;
printf("各点位置：%d %d %d dp[%d][%d]的值为：%d\n",a,b,c,i,j,dp[i][j]); */
}
}
int res=min(dp[n][1],min(dp[n][2],dp[n][3]));
cout<<res;
return 0;
}
正确代码：
#include<bits/stdc++.h>
using namespace std;
const int L=210,N=1010,INF=0x3f3f3f3f;
int g[L][L],f[N][L][L],p[N];
int main()
{
int l,n;
scanf("%d%d",&l,&n);
for(int i=1;i<=l;i++)
{
for(int j=1;j<=l;j++)
scanf("%d",&g[i][j]);
}
for(int i=1;i<=n;i++) scanf("%d",&p[i]);
memset(f,0x3f,sizeof(f));
p[0]=1;
f[0][2][3]=0;
for(int i=0;i<n;i++)
{
for(int x=1;x<=l;x++)
{
for(int y=1;y<=l;y++)
{
int z=p[i];
if(x==y||x==z||y==z) continue;
int v=f[i][x][y];
f[i+1][x][y]=min(f[i+1][x][y],v+g[p[i]][p[i+1]]);//p[i]->p[i+1]
f[i+1][z][y]=min(f[i+1][z][y],v+g[x][p[i+1]]);//x->p[i+1]
f[i+1][x][z]=min(f[i+1][x][z],v+g[y][p[i+1]]);//y->p[i+1]
}
}
}
int res=INF;
for(int x=1;x<=l;x++)
{
for(int y=1;y<=l;y++)
{
int z=p[n];
if(x==y||x==z||y==z) continue;
res=min(res,f[n][x][y]);
}
}
cout<<res;
return 0;
}