设有N*N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。 某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。
此人从A点到B点共走两次，试找出2条这样的路径，使得取得的数之和为最大。
输入格式
输入的第一行为一个整数N（表示N*N的方格图），接下来的每行有三个整数，前两个表示位置，第三个数为该位置上所放的数。一行单独的0表示输入结束。
输出格式
只需输出一个整数，表示2条路径上取得的最大的和。
-----------------------------------------------------------------------------------------------------------------------------------
这道题是动态规划的代表题目，使用的是所谓的“双线递归”，即假设有两个人同时从左上角开始走，假设两个人走到的位置是(x1,y1)和(x2,y2)，那么可以用f[x1][y1][x2][y2]表示此时可以获得的最大分值，转移方程为（map表示分值）：
f[x1][y1][x2][y2]
= max{f[x1 - 1][y1][x2 - 1][y2],f[x1 - 1][y1][x2][y2 - 1],f[x1][y1 - 1][x2 - 1][y2],f[x1][y1 - 1][x2][y2 - 1]} + map[x1][y1] + map[x2][y2] 当(x1,y1)和(x2,y2)不重合
= max{f[x1 - 1][y1][x2 - 1][y2],f[x1 - 1][y1][x2][y2 - 1],f[x1][y1 - 1][x2 - 1][y2],f[x1][y1 - 1][x2][y2 - 1]} + map[x1][y1] 当(x1,y1)和(x2,y2)重合
最后输出f[n][n][n][n]即可。
假如在方格左上角的左边再放一个格子(0,0)作为起点，到达右下角走的步数一定是2n - 1，并且x = step - y。根据上面的方程，f只和上一步有关系，因此，简化状态表示为f[k][x1][x2]，相应的转移方程可以参照上面写出。边界是f[0][0][0] = 0。
如果使用这种方法，还会发现f[k]只和f[k - 1]有关，因此可以采用滚动数组进一步优化空间。
C语言: 高亮代码由发芽网提供
01 #include <stdio.h>
02 #include <stdlib.h>
03
04 int n;
05 int map[11][11];
06 int f[25][15][15];
07 int di[4] = {1,1,0,0};
08 int dj[4] = {0,1,0,1};
09
10 int get_max(int a,int b)
11 {
12 if(a > b) return a;
13 return b;
14 }
15
16 int main()
17 {
18 int a,b,c;
19 int i,j,k,t;
20 int max;
21 scanf("%d",&n);
22 while(1)
23 {
24 scanf("%d%d%d",&a,&b,&c);
25 if(a == 0 && b == 0 && c == 0) break;
26 map[a][b] = c;
27 }
28 f[0][0][0] = 0;
29 for(k = 1;k <= 2 * n;k ++)
30 for(i = 1;i <= k;i ++)
31 for(j = 1;j <= k;j ++)
32 {
33 max = 0;
34 for(t = 0;t < 4;t ++)
35 max = get_max(max,f[k - 1][i - di[t]][j - dj[t]]);
36 if(i == j) f[k][i][j] = max + map[i][k - i + 1];
37 else f[k][i][j] = max + map[i][k - i + 1] + map[j][k - j + 1];
38 //printf("%d %d %d %d %d\n",i,k + 1 - i,j,k + 1 - j,f[k][i][j]);
39 }
40 printf("%d\n",f[2 * n - 1][n][n]);
41 return 0;
42 }
02 #include <stdlib.h>
03
04 int n;
05 int map[11][11];
06 int f[25][15][15];
07 int di[4] = {1,1,0,0};
08 int dj[4] = {0,1,0,1};
09
10 int get_max(int a,int b)
11 {
12 if(a > b) return a;
13 return b;
14 }
15
16 int main()
17 {
18 int a,b,c;
19 int i,j,k,t;
20 int max;
21 scanf("%d",&n);
22 while(1)
23 {
24 scanf("%d%d%d",&a,&b,&c);
25 if(a == 0 && b == 0 && c == 0) break;
26 map[a][b] = c;
27 }
28 f[0][0][0] = 0;
29 for(k = 1;k <= 2 * n;k ++)
30 for(i = 1;i <= k;i ++)
31 for(j = 1;j <= k;j ++)
32 {
33 max = 0;
34 for(t = 0;t < 4;t ++)
35 max = get_max(max,f[k - 1][i - di[t]][j - dj[t]]);
36 if(i == j) f[k][i][j] = max + map[i][k - i + 1];
37 else f[k][i][j] = max + map[i][k - i + 1] + map[j][k - j + 1];
38 //printf("%d %d %d %d %d\n",i,k + 1 - i,j,k + 1 - j,f[k][i][j]);
39 }
40 printf("%d\n",f[2 * n - 1][n][n]);
41 return 0;
42 }
No comments:
Post a Comment