和方格取数的分析一样

#include <iostream>
#include <algorithm>
using namespace std;
const int N=55;
int dp[2*N][N][N];
int a[N][N];
int main()
{int m,n;cin>>m>>n;//注意和方格取数不同的点在于是一个矩形不是正方形for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)cin>>a[i][j];//i最大为mfor(int k=2;k<=m+n;k++)for(int i1=1;i1<=m;i1++)for(int i2=1;i2<=m;i2++){//即使好心值为0，也会帮忙//所以只要注意两个路径不能有重复的点就可以了//如果有越界值，直接跳过if(k-i1<=0||k-i1>n||k-i2<=0||k-i2>n)continue;int t=a[i1][k-i1]+a[i2][k-i2];if(i1==i2)t-=a[i1][k-i1];int &x=dp[k][i1][i2];x=max(x,dp[k-1][i1][i2]);x=max(x,dp[k-1][i1-1][i2]);x=max(x,dp[k-1][i1-1][i2-1]);x=max(x,dp[k-1][i1][i2-1]);x+=t;}cout<<dp[m+n][m][m];
}