P1006 传纸条

链接

刚开始想的是两次01背包，把第一次走过的给记录下来。好像不太好记录，

参考了大佬的博客，数据范围不是很大，四维数组就可以了，

a,b第一个人走的，c,d代表第二个人

dp[a][b][c][d] = max{dp[a][b -1][c][d -1] , dp[a - 1][b][c -1][d],

                             dp[a][b -1][c -1][d],dp[a - 1][b][c][d -1]}+a[a][b] + a[c][d];

 只要保证纵坐标不一样就行，d = b + 1开始循环

最后输出是dp[n][m - 1][n - 1][m];

第一个人到第二个人只能往右或者往下走，所以到达的点是n,m-1

同理，第二个人到达的点是n-1,m;

如果卡的厉害，可以变为三维数组，怎么操作呢？

每次转移的时候，两个人走的步数是相等的，

枚举横坐标

k表示总的步数，

#include <bits/stdc++.h>

using namespace std;
int a[55][55],dp[110][55][55];
int n,m;

int main(){
    //freopen("in","r",stdin);
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    for(int k = 1; k <= n + m - 1; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(k - i < 0 || k - j < 0)
                    continue;
                dp[k][i][j] = max(max(dp[k - 1][i][j],dp[k - 1][i - 1][j - 1]),max(dp[k - 1][i][j - 1],dp[k - 1][i - 1][j])) + a[i][k - i + 1] + a[j][k - j + 1];
                if(i == j)
                    dp[k][i][j] -=  a[i][k - i + 1];
            }
        }
    }
    cout << dp[n + m - 1][n][n] << endl;
    return 0;
}