解法一
//第一种解法是对于方格取数问题变形加了特判,由于路径不能重合,在递归搜最大路径时对于上一条路径特判
//两条路径不能重合,当且仅当起点情况时能够重合,特判操作见注释
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int n, m;
int f[N + N][N][N];
int w[N][N];
int dx1[] = {0, 0, -1, -1}, dx2[] = {0, -1, 0, -1};
int dp(int k, int x1, int x2)
{
if(f[k][x1][x2] != -1) return f[k][x1][x2];
for(int i = 0; i < 4; i++)
{
int a = x1 + dx1[i], b = x2 + dx2[i];
if(a >= 1 && a < k && b >= 1 && b < k)
{
if((a != b) || (k == 3)) //特判操作
{
f[k][x1][x2] = max(f[k][x1][x2], dp(k - 1, a, b));
}
}
}
f[k][x1][x2] += w[x1][k - x1] + w[x2][k - x2];
return f[k][x1][x2];
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> w[i][j];
memset(f, -1, sizeof f);
f[2][1][1] = w[1][1];
cout << dp(n + m, n, n);
return 0;
}
解法二
//在自己写了一遍后,看了彩铅大佬的题解,发现这题即使有路径不能重合的操作,但是重合的最优路径都对应
//一条不重合路径,由于不重合是对题目加了限制,当我们解除这个限制的时候,答案不会变小,故用重合解法
//求得的答案必然大于等于本题的答案,又由于重合求得的答案可以对应一条不重合的情况,不重合的情况多走
//一个点但是必然多走的点权重为0,重合求得的答案对应一条不重合的路径,这条路径就是是符合条件的路径,
//故小于等于答案,又为重合情况下最优路径,故大于等于答案,即所求即答案
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int n, m;
int f[2 * N][N][N];
int w[N][N];
int dx1[] = {0, 0, -1, -1}, dx2[] = {-1, 0, -1, 0};
int dp(int k, int x1, int x2)
{
if(f[k][x1][x2] != -1) return f[k][x1][x2];
int t = w[x1][k - x1];
if(x1 != x2) t += w[x2][k - x2];
for(int i = 0; i < 4; i++)
{
int a = x1 + dx1[i], b = x2 + dx2[i];
if(a >= 1 && a < k && b >= 1 && b < k)
f[k][x1][x2] = max(f[k][x1][x2], dp(k - 1, a, b));
}
f[k][x1][x2] += t;
return f[k][x1][x2];
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
cin >> w[i][j];
memset(f, -1, sizeof f);
f[2][1][1] = w[1][1];
cout << dp(n + m, n, n);
return 0;
}