HZOJ 传纸条 动态规划

题面：

解题思路：

 用一个三维的数组来记录，dp[b][x1][x2]，b表示走的步数，表示两条路径上的某个点的横纵坐标相加之和,x1表示第一条路的某一点的横坐标，y1表示第一条路的某一点的纵坐标；x2表示第二条路的某一点的横坐标，y2表示第二条路的某一点的纵坐标。存在x1+y1=x2+y2=b(2<=b<=r+c)。

只要x1,x2,y1,y2不越界且，y1!=y2就可以保证两条路径无重复点。这两条路径都是从左上走到右下，且只能向下走或者向右走。那么dp[b][x1][x2]=max(

                 dp[b-1][x1][x2]（后退一步时，第一条路和第二条路都是从上面走来的）,

                 dp[b-1][x1-1][x2-1]（后退一步时，第一条路和第二条路都是从左面走来的）,

                 dp[b-1][x1-1][x2]（后退一步时，第一条路是从左面走来，第二条路都是从上面走来的）,

                 dp[b-1][x1][x2-1]（后退一步时，第一条路是上面走来，第二条路都是从左面走来的）,)+num[x1][y1]+num[x2][y2](这两个千万不能忘);

    最后，当走终点右下角的时候选择一个较大的路径max(dp[r+c-1][r][r-1],dp[r+c-1][r-1][r])+num[r][c];记得到所求结果,上述两个题目左上和右下角都为0所以就没有加，直接输出了。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <queue>
using namespace std;
int mapp[51][51],dp[105][51][51];
int main(){
    int n,m;
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> mapp[i][j];//输入各个点的值 
        } 
    }
    for(int b=2;b<=n+m;b++){//步数 
        for(int x1=1;x1<=n;x1++){
            for(int x2=1;x2<=n;x2++){
                int y1=b-x1;
                int y2=b-x2;
                if(y1>=1&&y1<=m&&y2>=1&&y2<=m&&y1!=y2){
                    dp[b][x1][x2]=max(max(dp[b-1][x1][x2],dp[b-1][x1-1][x2-1]),max(dp[b-1][x1-1][x2],dp[b-1][x1][x2-1]))
                    +mapp[x1][y1]+mapp[x2][y2];
                    
                }
                else continue;
            }
        } 
    }
    cout<<max(dp[m+n-1][n-1][n],dp[n+m-1][n][n-1])<<endl;
    return 0; 
}