【输入数据】

第一行有两个整数L,N(3<=L<=200, 1<=N<=1000)。L是位置数；N是请求数。每个位置从1到L编号。下L行每行包含L个非负整数。第i+1行的第j个数表示c(i,j) ，并且它小于2000。最后一行包含N个数，是请求列表。一开始三个服务员分别在位置1，2，3。

【输出数据】

一个数M，表示最小服务花费。

【输入样例】

【输出样例】

5

    又是一个历史遗留问题了，去年这个时候做的，当时比现在还菜所以没有深入研究此题，知道今天上午才圆满解决此题，很必要写一下题解纪念之~

   首先这个题应该是一道动规这是比较容易看出的， 那么方程是神马呢，这个也是容易想到的，f[i,j,k,p]表示前i个请求，第i次请求后三人分别在j,k,p三个位置上的最小代价，如果第i次请求要人去x位置那么：

f[i,x,k,p]:=min(f[i,x,k,p],f[i-1,j,k,p]+cost[j,x]); 

f[i,j,x,p]:=min(f[i,j,x,p],f[i-1,j,k,p]+cost[k,x]); 

f[i,j,k,x]:=min(f[i,j,k,x],f[i-1,j,k,p]+cost[p,x]);

这样的话需要枚举i,j,k,p就是m*N^3的算法肯定是过不了大数据的。

那么仔细想一下其实反正第i次请求必然有一个人到X处，而且三个人都是等价的，所以不必在意去的是哪个而是只管去的那个人是从什么地方去的，因此可以优化到3方即可，f[i,j,k]表示前i次请求后一个人在x处另外两个在j和k处的最优代价，因此：

如果第i次请求点在y，i+1次请求点在x那么转移方程就是：

f[i+1,j,k]:=min(f[i+1,j,k],f[i,j,k]+cost(y,x));

f[i+1,j,y]:=min(f[i+1,j,y],f[i,j,k]+cost(k,x));

f[i+1,y,k]:=min(f[i+1,y,k],f[i,j,k]+cost(j,x));

方程采用的是i点推i+1点的形式这个说实在这还是我第一次这么推，但是在这个题中感觉这样推更加方便明了。

下面详解一下代码以及注意吧：

program service；
var
  a:array[0..201,0..201] of longint;//a数组存的是从i到j的代价
  ask:array[0..1001] of longint;//ask数组存的是所有的询问
  f:array[0..1001,0..201,0..201] of longint;//f上面有解释不再重述
  n,m,i,j,ans,x,y,k:longint;
function min(a,b:longint):longint;
begin
  if a<b then exit(a) else exit(b);
end;
begin
  readln(n,m);
  for i:=1 to n do//读入
    for j:=1 to n do begin
    read(a[i,j]);
  end;
  ans:=maxlongint;
  for i:=1 to m do read(ask[i]);//读入
  fillchar(f,sizeof(f),$7);//初始化所以代价为最大值
  x:=ask[1];
  f[1,2,3]:=a[1,x];f[1,3,2]:=a[1,x];
  f[1,1,3]:=a[2,x];f[1,3,1]:=a[2,x];//这里是一个边界，因为最开始三人在1,2,3所以第一个询问后必然有这些
  f[1,1,2]:=a[3,x];f[1,2,1]:=a[3,x];//由于f[1,1,2]和f[1,2,1]不考虑2人顺序所以最好都作为边界（不这样其实也可以AC= =）
  for i:=1 to m-1 do begin//核心，转移过程
    x:=ask[i+1];y:=ask[i];
    for j:=1 to n do
      for k:=1 to n do if (y<>k) and (y<>j) and (j<>k) then begin//由于三人不能在同一位置所以必然y<>k<>j
        if (x<>j) and (x<>k) then f[i+1,j,k]:=min(f[i+1,j,k],f[i,j,k]+a[y,x]);//从y到x，x一定不能在j或k处
        if (x<>j) and (x<>y) then f[i+1,j,y]:=min(f[i+1,j,y],f[i,j,k]+a[k,x]);//从k到x，x一定不能在j或y处
        if (x<>k) and (x<>y) then f[i+1,y,k]:=min(f[i+1,y,k],f[i,j,k]+a[j,x]);//从j到x，x一定不能在k或y处
      end;//这里由于f[i,j,k]初始为极大值那么如果f[i,j,k]是无效状态则必然不会以其更新出i+1的三个状态故不必判断f[i,j,k]有效性
  end;
  for j:=1 to n do
    for k:=1 to n do ans:=min(ans,f[m,j,k]);
  writeln(ans);
end.

【特别注意】tyvj上有这道题但如果贴此代码你就悲剧了，因为这代码空间154超了已经，如果要用滚动数组的话，除了把方程中f[i]变成f[i mod 2]，还一定要注意在DP方程转移结束后加上f[i mod 2,j,k]:=1234567890；也就是说每一次用f[i mod 2]去更新f[(i+1) mod 2]后必须把f[i mod 2]赋为极大值，试想一下不这么做的话，f[1]更新f[2]，f[2]本来应该更新f[3]的，但是用了滚动f[3 mo2]=f[1]，用f[2]更新的f[3]必然没有原来的f[1]优，所以f[3 mod 2]的值一定是第一次f[1]中的值，因此用f[1]更新f[2]后必须把f[1]重新赋极大值。

【特别注意2】mod和div神马的弱爆了，统统用位运算，mod 2改为and 1,div 2改为shr 1,时间减少一倍有木有！！本来3秒多的点1秒半过了