NOIP 2008 传纸条

本题和NOIP2000的方格取数几乎相同，不过本题的要求是两条路线不交叉，而方格取数允许交叉，只不过一个位置取过后就变成0.

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

01 #include <stdio.h>
02 #include <stdlib.h>
03 #define MXN 55
04
05 int value[MXN][MXN];
06 int dx[4] = {0,-1,-1,0};
07 int dy[4] = {-1,0,-1,0};
08 long opt[MXN * 2][MXN][MXN] = {};
09 int v[MXN][MXN];
10 int m,n;
11
12 long get_max(long a,long b)
13 {
14     if(a > b)   return a;
15     return b;
16 }
17
18 int main()
19 {
20     scanf("%d%d",&m,&n);
21     int i,j,k,t;
22     int a,b;
23     long max;
24     for(i = 0;i < m;i ++)
25         for(j = 0;j < n;j ++)
26             scanf("%d",&v[i][j]);
27     opt[0][0][0] = 0;
28     for(k = 1;k < m + n;k ++)
29     {
30         for(i = 0;i < m && i <= k;i ++)
31             for(j = i;j < m && j <= k;j ++)  //请注意j的起始值，可以节省一部分时间
32             {
33                 max = 0;
34                 a = k - i;b = k - j;
35                 for(t = 0;t < 4;t ++)
36                 {
37                     if(i + dx[t] >= 0 && j + dy[t] >= 0)
38                         max = get_max(max,opt[k - 1][i + dx[t]][j + dy[t]]);
39                 }
40                 if(k == m + n - 2 || i != j)  //只有到最后位置才会计算i==j的情况，其他时候跳过
41                     opt[k][i][j] = max + v[i][a] + v[j][b];
42             }
43     }
44     printf("%ld\n",opt[m + n - 2][m - 1][m - 1]);
45     return 0;
46 }

网络上本题题解有很多使用的是方格取数的代码，几乎没有修改，亦可通过测试数据。
不过本人认为上面的代码更易于理解。