？？？

看直播的时候正解是dp，但我好像没用，请问为什么对了（我觉得对了）。

思路：分别对左上、左下、右上、右下四部分进行讨论，左上部分只有红色或黄色，左下部分只有黄色或绿色，右下部分只有绿色或橙色，左下部分只有红色或橙色，枚举每个将整个矩阵分成四部分的点并计算每部分的最大值，将四部分最大值之和取max就是最终结果。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N=2005;
int n,m;
long long a[N][N],lmax[N][N],rmax[N][N],lmin[N][N],rmin[N][N],lu[N][N],ru[N][N],ld[N][N],rd[N][N],sm,ans;
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) {
		for(int j=1;j<=m;j++) scanf("%lld",&a[i][j]);
	} 
	for(int i=1;i<=n;i++) {
		sm=0;
		for(int j=1;j<=m;j++) {
			sm+=a[i][j];
			lu[i][j]=lu[i][j-1]+lu[i-1][j]-lu[i-1][j-1]+a[i][j];
			lmax[i][j]=max(lmax[i][j-1],lmax[i-1][j]+sm);
		}
		sm=0;
		for(int j=m;j>=1;j--) {
			sm+=a[i][j];
			ru[i][j]=ru[i][j+1]+ru[i-1][j]-ru[i-1][j+1]+a[i][j];
			rmax[i][j]=max(rmax[i][j+1],rmax[i-1][j]+sm);
		}
	}
	for(int i=n;i>=1;i--) {
		sm=0;
		for(int j=1;j<=m;j++) {
			sm+=a[i][j];
			ld[i][j]=ld[i+1][j]+ld[i][j-1]-ld[i+1][j-1]+a[i][j];
			lmin[i][j]=min(lmin[i][j-1],lmin[i+1][j]+sm);
		}
		sm=0;
		for(int j=m;j>=1;j--) {
			sm+=a[i][j];
			rd[i][j]=rd[i+1][j]+rd[i][j+1]-rd[i+1][j+1]+a[i][j];
			rmin[i][j]=min(rmin[i][j+1],rmin[i+1][j]+sm);
		}
	}
	ans=-1e18;
	for(int i=0;i<=n;i++) {
		for(int j=0;j<=m;j++) {
			ans=max(ans,lmax[i][j]*3+(lu[i][j]-lmax[i][j])*1+lmin[i+1][j]*3+(ld[i+1][j]-lmin[i+1][j])*4+rmin[i+1][j+1]*2+(rd[i+1][j+1]-rmin[i+1][j+1])*4+rmax[i][j+1]*2+(ru[i][j+1]-rmax[i][j+1])*1);
		}
	}
	printf("%lld\n",ans);
	return 0;
}

这个帖子应该不违规吧