首页 > 代码库 > wioi 1043--方格取数

wioi 1043--方格取数

2024-07-09 23:55:35   224人阅读

题目描述：

设有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         else27             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\n",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\n",operDp(n));42     }43     return 0;44 }

 


联系
我们