首先有一个比较明显的状态设计：设 \(dp_{x1,y1,x2,y2}\) 表示第一条路线走到 \((x1,y1)\) ，第二条路线走到 \((x2,y2)\) 的路径上的数的和的最大值。
这个状态设计是可以通过本题的，但其实还有更加简洁的状态设计。
我们设 \(dp_{k,x1,x2}\) 表示第一条路线和第二条路线分别走了 \(k\) 步，其中第一条路线走到了 \((x1,k - x1)\) ，第二条路线走到了 \((x2, k - x2)\) 的路径上的数的和的最大值。
关于 \(x1\) 和 \(x2\) 的取值范围：因为 \(1 \leq x1,x2 \leq n\) ，且 \(1 \leq k-x1, k-x2 \leq m\) ，所以我们可以得出 \(\max(1,k-m) \leq x1,x2 \leq \min(k-1,n)\) 。
由于每一次移动只能向下或向右，因此转移就比较明显了，这里不再赘述。
如果两条路径没有重叠，那么就可以分别加上 \((x1,k-x1)\) 和 \((x2,k-x2)\) 位置上的数。
注意答案要输出 \(dp_{n+m,n,n}\) ,不是 \(dp_{n+m,n,m}\) 。
#include <bits/stdc++.h>
#define DEBUG fprintf(stderr, "Passing [%s] line %d\n", __FUNCTION__, __LINE__)
#define itn int
#define gI gi
using namespace std;
typedef long long LL;
typedef pair <int, int> PII;
typedef pair <int, PII> PIII;
inline int gi()
{
int f = 1, x = 0; char c = getchar();
while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return f * x;
}
const int maxn = 53;
int n, m, a[maxn][maxn], dp[maxn * 2][maxn][maxn], ans = 0;
int main()
{
//freopen(".in", "r", stdin);
//freopen(".out", "w", stdout);
n = gi(), m = gi();
for (int i = 1; i <= n; i+=1)
{
for (int j = 1; j <= m; j+=1)
{
a[i][j] = gi();
}
}
for (int k = 1; k <= n + m; k+=1)
{
for (int x1 = max(1, k - m); x1 <= min(k - 1, n); x1+=1)
{
for (int x2 = max(1, k - m); x2 <= min(k - 1, n); x2+=1)
{
//计算出新增加的数的和
int t = a[x1][k - x1];
if (x1 != x2) t += a[x2][k - x2];
//转移状态
int &v = dp[k][x1][x2];
v = max(v, dp[k - 1][x1][x2] + t);
v = max(v, dp[k - 1][x1 - 1][x2] + t);
v = max(v, dp[k - 1][x1][x2 - 1] + t);
v = max(v, dp[k - 1][x1 - 1][x2 - 1] + t);
}
}
}
//输出答案
printf("%d\n", dp[n + m][n][n]);
return 0;
}