[Swust OJ 1084]--Mzx0821月赛系列之情书(双线程dp)

题目链接：http://acm.swust.edu.cn/problem/1084/

Time limit(ms): 1000　　　　　　　　Memory limit(kb): 65535

 

Description

小时候，Mzx0821暗恋班上的一个妹子Zzx。

一次班上做活动，班上同学被安排坐成m行n列的矩阵，Mzx0821坐在坐标（x1,y1）的位置，Zzx坐在坐标（x2,y2）的位置。活动过程中，Mzx0821写了一张纸条想给Zzx，但是Mzx0821又不想班上其他人看到他写的内容，于是Mzx0821给班上每个人定义了一个保密程度值（就是这个人不偷看纸条内容的可能），每个人传递纸条只能给前后左右的人。

Mzx0821还考虑到万一Zzx给Mzx0821回纸条怎么办呢，为了保密，Mzx0821希望每个人最多传递一次纸条，就是说一个人在Mzx0821传给Zzx的时候帮了忙，就不能再帮Zzx传给Mzx0821，反之亦然。

Mzx0821希望找到这样两条路，使得来回两条路上的保密程度值的和最大，为了尽快传到，这两条路必须是Mzx0821到Zzx的之间的最短路。

Mzx0821智商实在捉急，于是向机智的学弟学妹们求助，你能帮助他找到正确的路线吗？

Input

输入第一行有2个用空格隔开的整数m和n，表示班里有m行n列（1<=m,n<=50）。

为了简化问题我们假设Mzx0821坐在左上角，Zzx坐在右下角。

接下来的m行是一个m*n的矩阵，矩阵中第i行j列的整数表示坐在第i行j列的学生的保密程度。每行的n个整数之间用空格隔开。

友情提示：Mzx0821坐标点的值和Zzx坐标点的值为0，坐标点的值<10000。

 

Output

输出共一行，包含一个整数，表示来回两条路上参与传递纸条的学生的保密程度之和的最大值。

 

Sample Input

3 3 0 3 9 2 8 5 5 7 0

Sample Output

34

 

输出换行请使用\r\n

 

 

解题思路：一个简单的双线程dp，直接写就是了，两个人同一个方向同时走,dp[i][j][x][y]，代表第一个人走到(i,j)，第二个人走到(x,y)的最大值

 

我们转化一下思想，题目中说由左上方到右下方来回，我们可以看作是从左上方找两条不相交的路径到右下方。这里我们可以好比是两个纸条同时从左上方向右下方传，只要保证在同一时刻两个纸条不在同一个人手里，那么我们就能保证两个字条的路径不相交.

　　确定算法： DP（动态规划）
　　状态：当前时刻的两个字条的坐标。

　　状态转移方程式 :

　　dp[i][j][x][y]= max{ dp[i-1][j][x-1][y],dp[i-1][j][x][y-1],dp[i][j-1][x-1][y],dp[i][j-1][x][y-1] }+mpt[i][j]+mpt[x][y]

　　为了保证两个字条是同步传递的，所以方程式要加一个限定条件 ( i + j = x + y )☆

 

代码如下：

 #include<iostream>
 #include<cstring>
 #include<algorithm>
 using namespace std;

 #define maxn 51
 int m, n, mpt[maxn][maxn];
 int dp[maxn][maxn][maxn][maxn];
 //同一个方向同时走
 //dp[i][j][x][y]代表当第一个人走到i,j且第二个人走到x,y时的最大值

 int max(int x, int y, int z, int w){
     return max(max(max(x, y), z), w);
 }
 int main()
 {
     while (cin >> m >> n){
         memset(dp, , sizeof(dp));
         for (int i = ; i <= m; i++)
         for (int j = ; j <= n; j++)
             cin >> mpt[i][j];
         for (int i = ; i <= m; i++){
             for (int j = ; j <= n; j++){
                 //第二个人走的路径在第一个人的下面，
                 for (int x = i + ; x <= m; x++){
                     int y = i + j - x;
                     if (y <= )continue;
                     dp[i][j][x][y] = max(dp[i - ][j][x - ][y], dp[i - ][j][x][y - ], dp[i][j - ][x][y - ], dp[i][j - ][x - ][y]) + mpt[i][j] + mpt[x][y];
                 }
             }
         }
         //最后第一个人到终点的左边，第二个人到终点的右边
         cout << dp[m - ][n][m][n - ] << "\r\n";
     }
     return ;
 }

代码还可以优化成三维数组：

 #include<iostream>
 #include<cstring>
 #include<algorithm>
 using namespace std;

 #define maxn 51
 int m, n, mpt[maxn][maxn];
 int dp[maxn][maxn][maxn];
 //同一个方向同时走

 int max(int x, int y, int z, int w){
     return max(max(max(x, y), z), w);
 }
 int main()
 {
     while (cin >> m >> n){
         memset(dp, , sizeof(dp));
         for (int i = ; i <= m; i++)
         for (int j = ; j <= n; j++)
             cin >> mpt[i][j];
         for (int i = ; i <= m; i++){
             for (int j = ; j <= n; j++){
                 for (int x = ; x < i; x++){
                     dp[i][j][x] = max(dp[i - ][j][x - ], dp[i - ][j][x], dp[i][j - ][x - ], dp[i][j - ][x]) + mpt[i][j] + mpt[x][i + j - x];
                 }
             }
         }
         //最后第一个人到终点的左边，第二个人到终点的右边
         cout << dp[m][n - ][m - ] << "\r\n";
     }
     return ;
 }