題意：
有三個(gè)郵遞員A,B,C
一開始分別在地點(diǎn)1,2,3(M<=200)，給定矩陣G，G[i][j]滿足G[i][j]<=G[i][k]+G[k][j]，表示i到
j的代價(jià)，每天有一封郵件(共N<=1000)在第Ni個(gè)地點(diǎn)，需要派一個(gè)郵遞員過去，不能有兩個(gè)人在同一地點(diǎn)，每次只能移動(dòng)一個(gè)人。
做
法：
出題人沒有道德 這個(gè)題是CEOI2005的service
考慮樸素做法F[T][i][j][k]表示第T天，三個(gè)郵遞員各在
i,j,k，轉(zhuǎn)移即枚舉哪個(gè)人去。
有個(gè)優(yōu)化 規(guī)定i<j<k 可以優(yōu)化一般。
但是這個(gè)復(fù)雜度是無法通過此題的
注意到
第i天必然有個(gè)人要去Ni，所以可以將F[T][i][j][k]減到F[i][j][k]表示第i天另外兩個(gè)郵遞員在j,k
最后規(guī)定
j<k，將i維滾動(dòng)，便完成了此題。
（原題還要求輸出方案 在64M內(nèi)存情況下只能用unsigned
char記錄方案，較惡心）
1 #include <cstdio>
2 #include <cstring>
3 int N,Q,G[205][205],list[1005];
4 int F[2][205][205];
5 inline void Update(int &u,int v)
6 {
7 if (u>v||u<0) u=v;
8 }
9 int main()
10 {
11 scanf("%d",&N);
12 for (int i=1;i<=N;++i)
13 for (int j=1;j<=N;++j)
14 scanf("%d",&G[i][j]);
15 for (;scanf("%d",&list[++Q])!=EOF;);
16 --Q;
17 memset(F[1],-1,sizeof(F[1]));
18 F[1][2][3]=G[1][list[1]];
19 F[1][1][3]=G[2][list[1]];
20 F[1][1][2]=G[3][list[1]];
21 for (int i=1,pre=1;i<Q;++i,pre^=1)
22 {
23 memset(F[pre^1],-1,sizeof(F[pre^1]));
24 for (int j=1;j<N;++j)
25 for (int k=j+1;k<=N;++k)
26 if (F[pre][j][k]>=0)
27 {
28 if (list[i+1]!=j&&list[i+1]!=k)
29 Update(F[pre^1][j][k],F[pre][j][k]+G[list[i]][list[i+1]]);
30 if (list[i+1]!=list[i]&&list[i+1]!=k)
31 if (k<list[i]) Update(F[pre^1][k][list[i]],F[pre][j][k]+G[j][list[i+1]]);
32 else Update(F[pre^1][list[i]][k],F[pre][j][k]+G[j][list[i+1]]);
33 if (list[i+1]!=list[i]&&list[i+1]!=j)
34 if (j<list[i]) Update(F[pre^1][j][list[i]],F[pre][j][k]+G[k][list[i+1]]);
35 else Update(F[pre^1][list[i]][j],F[pre][j][k]+G[k][list[i+1]]);
36 }
37 }
38 int ret=1<<30;
39 for (int i=1;i<N;++i)
40 for (int j=i+1;j<=N;++j)
41 if (F[Q&1][i][j]>=0)
42 Update(ret,F[Q&1][i][j]);
43 printf("%d\n",ret);
44 return 0;
45 }
46