USACO Canadan Tour

容易发现，我们要做的就是找到两条路径，使它们符合下列限制的前提下，使两条路径上的点数和最大（起点重点各计算一次）
1）一直都是从东到西走的
2）除了起点和终点，两条路径没有其他公共点

很容易就可以发现这个问题有重复嵌套的子问题，因此想到了用动态规划解决。
用max[i][j]表示从起始点（用1表示） 到i，j的两条符合上述限制条件的路径的点数和的最大值。我们最终要求的就是max[N][N]。
容易知道max[i][j] = max[j][i]，因此我们规定i < j，接下来就是写出转移方程。
作几个示意图可以发现，max[i][j] = getmax{max[i][k] + 1}   if(1 <= k < j && k has an edge to j)
由于k与i的关系在计算过程中会变化，加上写程序的时候脑子比较乱，所以就采用了记忆化搜索，代码如下。

C语言: 高亮代码由发芽网提供

01 #include <stdio.h>
02 #include <stdlib.h>
03 #include <string.h>
04 #define MIN -1000
05
06 int adj[101][101];
07 int V,N;
08 int opt[101][101];
09 int solved[101][101];
10 char city[101][20];
11
12 void init()    //读入地名，构建邻接矩阵
13 {
14     int i,j;
15     int b,e;
16     char from[20],to[20];
17     scanf("%d%d\n",&N,&V);
18     for(i = 1;i <= N;i ++)
19         scanf("%s\n",city[i]);
20     for(i = 0;i < V;i ++)
21     {
22         scanf("%s %s\n",from,to);
23         if(strcmp(from,to) == 0)    continue;
24         for(j = 1;j <= N;j ++)
25         {
26             if(strcmp(from,city[j]) == 0)    b = j;
27             else if(strcmp(to,city[j]) == 0)    e = j;
28         }
29         adj[e][b] = adj[b][e] = 1;
30     }
31 }
32
33 int getmax(int a,int b)
34 {
35     if(a > b)    return a;
36     return b;
37 }
38
39 int dp(int a,int b)
40 {
41     if(a > b)   //保证a <= b
42     {
43         int tmp;
44         tmp = a;
45         a = b;
46         b = tmp;
47     }
48     if(a == 1 && b == 1)    return 1;
49     if(a == b && a != N)    return MIN;   //不允许的情况
50     if(solved[a][b])
51         return opt[a][b];
52     int i,max = MIN;
53     for(i = 1;i < b;i ++)
54         if(adj[i][b])
55             max = getmax(max,dp(a,i) + 1);
56     opt[a][b] = max;
57     solved[a][b] = 1;
58     return opt[a][b];
59 }
60
61 int main()
62 {
63     int ans;
64     freopen("tour.in","r",stdin);
65     freopen("tour.out","w",stdout);
66     init();
67     ans = dp(N,N) - 1;
68     if(ans < 1)    printf("1\n");  //无解的情况
69     else    printf("%d\n",ans);
70     return 0;
71 }