wioi 1043--方格取数

题目描述：

设有N*N的方格图(N<=10,我们将其中的某些方格中填入正整数,而其他的方格中则放入数字0。如下图所示（见样例）：

某人从图的左上角的A 点出发，可以向下行走，也可以向右走，直到到达右下角的B点。在走过的路上，他可以取走方格中的数（取走后的方格中将变为数字0）。

此人从A点到B 点共走两次，试找出2条这样的路径，使得取得的数之和为最大。

思路：

（1）dp，4维，dp[i1,j1,i2,j2]表示两条路分别走到（i1,j1）点和（i2,j2）点时取到的最大值

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int a[11][11];
 7 int dp[11][11][11][11];
 8 const int INF = 999999999;
 9 
10 int operDp(int n)
11 {
12     int i1, j1, i2, j2;
13     memset(dp,0,sizeof(dp));
14     for(i1 = 1; i1 <= n; i1++)
15     for(j1 = 1; j1 <= n; j1++)
16     for(i2 = 1; i2 <= n; i2++)
17     for(j2 = 1; j2 <= n; j2++)
18     {
19         int tmp = -INF;
20         tmp = max(tmp, dp[i1-1][j1][i2-1][j2]);
21         tmp = max(tmp, dp[i1-1][j1][i2][j2-1]);
22         tmp = max(tmp, dp[i1][j1-1][i2-1][j2]);
23         tmp = max(tmp, dp[i1][j1-1][i2][j2-1]);
24         if(i1 == i2 && j1 == j2)
25             dp[i1][j1][i2][j2] = tmp + a[i1][j1];
26         else
27             dp[i1][j1][i2][j2] = tmp + a[i1][j1] + a[i2][j2];
28     }
29     return dp[n][n][n][n];
30 }
31 
32 int main()
33 {
34     int n, r, c, v;
35     while(scanf("%d",&n) != EOF)
36     {
37         memset(a,0,sizeof(a));
38         while(true)
39         {
40             scanf("%d%d%d",&r,&c,&v);
41             if(!r && !c && !v) break;
42             a[r][c] = v;
43         }
44         printf("%d
",operDp(n));
45     }
46     return 0;
47 }

(2)降低dp状态的维数

dp[k][i][j]表示走了k步，第一条路向右走了i步，第二条路向右走了j步；k最大值是向下走了n，向右走了n，也就是2*n

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 
 6 int a[11][11];
 7 int dp[21][11][11];
 8 const int INF = 999999999;
 9 
10 int operDp(int n)
11 {
12     int i, j, k;
13     memset(dp,0,sizeof(dp));
14     for(k = 1; k <= 2 * n; k++)
15     for(i = 1; i <= k; i++)
16     for(j = 1; j <= k; j++)
17     {
18         int tmp = -INF;
19         tmp = max(tmp, dp[k-1][i-1][j-1]);
20         tmp = max(tmp, dp[k-1][i-1][j]);
21         tmp = max(tmp, dp[k-1][i][j-1]);
22         tmp = max(tmp, dp[k-1][i][j]);
23         if(i == j) dp[k][i][j] = tmp + a[k-i+1][i];
24         else dp[k][i][j] = tmp + a[k-i+1][i] + a[k-j+1][j];
25     }
26     return dp[2*n][n][n];
27 }
28 
29 int main()
30 {
31     int n, r, c, v;
32     while(scanf("%d",&n) != EOF)
33     {
34         memset(a,0,sizeof(a));
35         while(true)
36         {
37             scanf("%d%d%d",&r,&c,&v);
38             if(!r && !c && !v) break;
39             a[r][c] = v;
40         }
41         printf("%d
",operDp(n));
42     }
43     return 0;
44 }