表示这个题想的很dt。
一开始就想f[i,a,b,c]表示第i个请求，三个人在a，b，c的最小代价。但是肯定是杀伤力超大任何评测机都闻风丧胆的TLE+MLE程序……
后来就想能不能把i压缩掉，结果想了很长时间无果，发现如果第i时间那么它上一次一定有一个点是i-1要求的位置，还是不能搞，因为不知道怎嘛把i去掉……
后来无语看了题解，发现是把a,b,c中压缩了一维，因为对于确定的i，至少有一个人的位置是确定的。
所以用f[i,a,b]表示，在第i个请求中，三个人分别在a,b,p[i]的最小代价。p[i]就是请求位置。
最好用主动更新，f[i-1,a,b]去更新。
如果是从p[i-1]到p[i]，那么f[i,a,b]:=min(f[i,a,b],f[i-1,a,b]+c[p[i-1],p[i]]);
如果是a到p[i]，那么f[i,p[i-1],b]:=min(f[i,p[i-1],b],f[i-1,a,b]+c[a,p[i]]);
如果是b到p[i]，那么f[i,a,p[i-1]]:=min(f[i,a,p[i-1]],f[i-1,a,b]+c[b,p[i]]);
好了，一开始把第一个询问赋初值，循环就行了。还有，需要滚动数组，开上面的状态也会开爆的……
View Code var f:array[0..1,1..200,1..200] of longint; c:array[1..200,1..200] of longint; p:array[1..1000] of longint; n,m:longint; ans,i,j,k:longint;function min(a,b:longint):longint;beginif a>b then exit(b) else exit(a);end;begin readln(n,m);for i:=1 to n dofor j:=1 to n do read(c[i,j]);for i:=1 to m do read(p[i]); filldword(f,sizeof(f) shr 2,maxlongint); f[0,2,3]:=c[1,p[1]]; f[0,1,2]:=c[3,p[1]]; f[0,1,3]:=c[2,p[1]];for i:=2 to m dobeginfor j:=1 to n dofor k:=1 to n doif (f[0,j,k]<>maxlongint) and (j<>k) and (k<>p[i-1]) and (j<>p[i-1]) then begin f[1,j,k]:=min(f[1,j,k],f[0,j,k]+c[p[i-1],p[i]]); f[1,p[i-1],k]:=min(f[1,p[i-1],k],f[0,j,k]+c[j,p[i]]); f[1,j,p[i-1]]:=min(f[1,j,p[i-1]],f[0,j,k]+c[k,p[i]]);end;for j:=1 to n dofor k:=1 to n dobegin f[0,j,k]:=f[1,j,k]; f[1,j,k]:=maxlongint;end;end; ans:=maxlongint;for i:=1 to n dofor j:=1 to n dobegin ans:=min(ans,f[0,i,p[m]]); ans:=min(ans,f[0,p[m],j]); ans:=min(ans,f[0,i,j]);end; writeln(ans);end.转载于:https://www.cnblogs.com/zjerly/archive/2011/10/20/2218744.html
相关资源：JAVA上百实例源码以及开源项目