题意描述：一个城市中的道路网络是一个完全图，每对顶点间有权值。要在所有N个地区发放报纸。开始3辆发报车都在A城市，然后每步只能移动一辆发报车，并且vi被访问当且仅当vi-1被访问过。求发完报纸需要的最少时间。
这道题正是第二个条件使得状态具备了阶段性。可以用{now,p1,p2,p3}表示状态，now代表已经发完了几个城市，p1,p2,p3分别为三辆发报车停的位置。然后状态转移就很简单了，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]}
当然，p1,p2,p3可以用最小表示法优化下，可以省去很多本质上相同的状态。由于节点数太少，就懒的优化了- -
贴代码
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 }