板子题

/*
 * @Author: YMYS
 * @Date: 2024-12-18 08:48:33
 * @LastEditTime: 2024-12-18 09:02:41
 * @FilePath: \VScode-C&C++-Coding\Acwing\算法提高课\1.动态规划\1.数字三角形模型\4.传纸条.cpp
 * @URL:https://www.acwing.com/problem/content/277/
 * @Description: 275. 传纸条
 * 思路：
 * 拿到这道题，根据题意我以为是从左上和右下两个点开始遍历，找最大和即可
 * 但是我们不能这么想，因为图中给的样例，假设左上角的人走的0 3 8 7 0，那这样右下角的人就无法传递纸条传回左上角了
 * 所以我仔细想了一下发现：从右下到左上其实等同于从左上到右下
 * 也就是说：我们可以看成有两个人同时从左上出发，然后不取相同的点
 * 那就和方格取数是一个道理了
 * 那么开始敲代码吧！
*/
#include<bits/stdc++.h>

using namespace std;

const int N = 55;

int m,n;//m行n列
int w[N][N];
int dp[2*N][N][N];

int main()
{
#ifdef ABC
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin);
    freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout);
#endif
    cin>>m>>n;

    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            cin>>w[i][j];
        }
    }

    for(int k=1;k<=m+n;k++){
        for(int i1=1;i1<=m;i1++){
            for(int i2=1;i2<=m;i2++){
                int j1 = k-i1, j2 = k-i2;

                if(j1 >= 1 && j1<=n && j2 >= 1 && j2 <= n){
                    int t = w[i1][j1];
                    if(i1!=i2) t+=w[i2][j2];

                    int &x = dp[k][i1][i2];
                    x = max(x, dp[k-1][i1-1][i2-1]+t);
                    x = max(x, dp[k-1][i1][i2-1]+t);
                    x = max(x, dp[k-1][i1-1][i2]+t);
                    x = max(x, dp[k-1][i1][i2]+t);
                }
            }
        }
    }

    cout<<dp[m+n][m][m]<<endl;

    return 0;
}