一个公司有三个移动服务员，最初分别在位置?1，2，3 处。
如果某个位置（用一个整数表示）有一个请求，那么公司必须指派某名员工赶到那个地方去。
某一时刻只有一个员工能移动，且不允许在同样的位置出现两个员工。
从?pp?到?qq?移动一个员工，需要花费?c(p,q)。
这个函数不一定对称，但保证?c(p,p)=0。
给出?NN?个请求，请求发生的位置分别为?p1～pN。
公司必须按顺序依次满足所有请求，且过程中不能去其他额外的位置，目标是最小化公司花费，请你帮忙计算这个最小花费。
输入格式
第?11?行有两个整数?L,N，其中?L?是位置数量，N 是请求数量，每个位置从?1?到?L?编号。
第?2?至?L+1 行每行包含?L?个非负整数，第?i+1 行的第?j?个数表示?c(i,j)，并且它小于?2000。
最后一行包含?N?个整数，是请求列表。
一开始三个服务员分别在位置?1，2，3。
输出格式
输出一个整数?M，表示最小花费。
数据范围
3≤L≤200,
1≤N≤1000
输入样例：
5 9
0 1 1 1 1
1 0 2 3 2
1 1 0 4 1
2 1 5 0 1
4 2 3 4 0
4 2 4 1 5 4 3 2 1
输出样例：
5解题思路：状态表示：首先最有可能想到的是f[i][x][y][z]，表示当前处理完第i个服务后，3个快递员的状态，但是通过计算时间和空间，200^3*1000=8e9，显然超出了时间和空间的限制，那就要开始想办法去优化状态表示，因为是处理完了第i个服务，所以此时一定有一个快递员站在第i个服务地点的位置，这样我们就可以省略一维数组，发现刚刚好。
状态计算：一般动态规划的状态计算大多是已知当前的状态，去找上一步状态，由那些状态可以得到当前的状态，但是我们分析一个这个题目，当前状态的前一步是会有很多种可能的，所以这里罕见地使用了另一种方法从当前的状态出发去更新能到达的下一个状态，现在我们已知f[i][x][y]，要去得到下一个状态，令z=p[i],下一步就是要派遣一个快递员去往p[i+1]地点，那我们就有3种选择
1、派z去，就是f[i+1][x][y]（x，y待在原位置不动）。
2、派x去，就是f[i+1][z][y]（用z替换x的状态，此时x站在了p[i+1]位置上）
3、派y去，就是f[i+1][x][z]（用z替换y的状态，此时y站在了p[i+1]位置上）
到最后一步，1个快递员站在了第p[n]个位置上，而其他2个快递员是随机的，所以枚举x,y，取f[n][x][y]中的最小值即可
上代码：
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1010,M=210;
int f[N][M][M];
int l,n;
int c[M][M],p[N];
int main()
{
cin>>l>>n;
for(int i=1;i<=l;i++)
for(int j=1;j<=l;j++)
cin>>c[i][j];
for(int i=1;i<=n;i++)
cin>>p[i];
p[0]=3;
memset(f,0x3f3f3f3f,sizeof f);
f[0][1][2]=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],u=p[i+1],v=f[i][x][y];
if(x==y||x==z||y==z)
continue;
f[i+1][x][y]=min(f[i+1][x][y],v+c[z][u]);
f[i+1][z][y]=min(f[i+1][z][y],v+c[x][u]);
f[i+1][x][z]=min(f[i+1][x][z],v+c[y][u]);
}
int res=0x3f3f3f3f;
for(int x=1;x<=l;x++)
for(int y=1;y<=l;y++)
{
if(x==y||y==p[n]||x==p[n])
continue;
res=min(res,f[n][x][y]);
}
cout<<res<<endl;
return 0;
}
