題意描述：一個(gè)城市中的道路網(wǎng)絡(luò)是一個(gè)完全圖，每對頂點(diǎn)間有權(quán)值。要在所有N個(gè)地區(qū)發(fā)放報(bào)紙。開始3輛發(fā)報(bào)車都在A城市，然后每步只能移動一輛發(fā)報(bào)車，并且vi被訪問當(dāng)且僅當(dāng)vi-1被訪問過。求發(fā)完報(bào)紙需要的最少時(shí)間。
這道題正是第二個(gè)條件使得狀態(tài)具備了階段性。可以用{now,p1,p2,p3}表示狀態(tài)，now代表已經(jīng)發(fā)完了幾個(gè)城市，p1,p2,p3分別為三輛發(fā)報(bào)車停的位置。然后狀態(tài)轉(zhuǎn)移就很簡單了，dp[now][p1][p2][p3]=min{dp[now-1][now-1][p2][p3],dp[now-1][p1][now-1][p2][p3],dp[now-1][p1]p2][now-1]}
當(dāng)然，p1,p2,p3可以用最小表示法優(yōu)化下，可以省去很多本質(zhì)上相同的狀態(tài)。由于節(jié)點(diǎn)數(shù)太少，就懶的優(yōu)化了- -
貼代碼
1 # include <cstdio>
2 # include <cstring>
3 using namespace std;
4 int map[40][40];
5 int dp[31][31][31][31];
6 bool inq[31][31][31][31];
7 int q[1000000][4],s,e;
8 int main()
9 {
10 int testcase;
11 scanf("%d",&testcase);
12 while(testcase--)
13 {
14 int num;
15 memset(dp,-1,sizeof(dp));
16 memset(map,-1,sizeof(map));
17 memset(inq,false,sizeof(inq));
18 scanf("%d",&num);
19 for(int i=0;i<num-1;i++)
20 for(int j=i+1;j<num;j++)
21 {
22 scanf("%d",&map[i][j]);
23 map[j][i]=map[i][j];
24 }
25 s=e=-1;
26 inq[0][0][0][0]=true;
27 dp[0][0][0][0]=0;
28 e++;
29 q[e][0]=q[e][1]=q[e][2]=q[e][3]=0;
30 int res=0xfffffff;
31 while(s!=e)
32 {
33 s++;
34 inq[q[s][0]][q[s][1]][q[s][2]][q[s][3]]=false;
35 if(q[s][0]==num-1)
36 res=(dp[q[s][0]][q[s][1]][q[s][2]][q[s][3]]<res?dp[q[s][0]][q[s][1]][q[s][2]][q[s][3]]:res);
37 else
38 {
39 for(int i=1;i<=3;i++)
40 {
41 int p[4]={q[s][0],q[s][1],q[s][2],q[s][3]};
42 p[i]=++p[0];
43 if(dp[p[0]][p[1]][p[2]][p[3]]==-1||dp[p[0]][p[1]][p[2]][p[3]]>dp[q[s][0]][q[s][1]][q[s][2]][q[s][3]]+map[q[s][i]][p[0]])
44 {
45 dp[p[0]][p[1]][p[2]][p[3]]=dp[q[s][0]][q[s][1]][q[s][2]][q[s][3]]+map[q[s][i]][p[0]];
46 if(!inq[p[0]][p[1]][p[2]][p[3]])
47 {
48 inq[p[0]][p[1]][p[2]][p[3]]=true;
49 e++;
50 q[e][0]=p[0];
51 q[e][1]=p[1];
52 q[e][2]=p[2];
53 q[e][3]=p[3];
54 }
55 }
56 }
57 }
58 }
59 printf("%d\n",res);
60 }
61 return 0;
62 }