就是个普及组 $dp$ 合集，把 $NOI$ 从左到右拆成 $9$ 个部分，每个部分都可以分别 $dp$
除了 $N$ 的中间部分比较恶心以外其他都还好，自己推一下然后就知道转移，就 $N$ 的中间优化转移比较不好写
随便吧，反正 $9$ 个 $dp$ 都挺简单的，量变导致质变，我在想那一年的选手是不是都被恶心到了...反正我是被恶心死了
$luogu$ 上这一题空间限制太小了，原题是 $512MB$ ，所以这份代码在 $luogu$ 过不去（我都滚动数组了啊...）
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=157,M=507; int n,m,sum[N][M],ans; int f[2][M][N][N],mx[M][N][N],mxx,mxxx[N][N]; inline int calc(int x,int l,int r) { return sum[r][x]-sum[r][x-1]-sum[l-1][x]+sum[l-1][x-1]; } int main() { n=read(),m=read(); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+read(); memset(f,~0x3f,sizeof(f)); memset(mx,~0x3f,sizeof(mx)); for(int j=1;j<=n;j++) for(int k=j;k<=n;k++) f[0][0][j][k]=0; for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) for(int k=j;k<=n;k++) f[0][i][j][k]=max(0,f[0][i-1][j][k])+calc(i,j,k); for(int i=2;i<=m;i++) for(int j=1;j<=n;j++) for(int k=n-1;k>=j;k--) mx[i][j][k]=max(mx[i][j][k+1],f[0][i-1][j][k+1]); for(int i=1;i<=m;i++) { memset(mxxx,~0x3f,sizeof(mxxx)); for(int k=n;k>=1;k--) for(int j=1;j<=k;j++) mxxx[j][k]=max(mxxx[j-1][k],f[1][i-1][j][k]); for(int j=1;j<=n;j++) { mxx=mxxx[j-1][j-1]; for(int k=j;k<=n;k++) { mxx=max(mxx,mxxx[j][k]); f[1][i][j][k]=max(mx[i][j][k],mxx)+calc(i,j,k); } } } memset(mx,~0x3f,sizeof(mx)); memset(f[0],~0x3f,sizeof(f[0])); for(int i=1;i<=m;i++) for(int k=1;k<=n;k++) for(int j=k-1;j>=1;j--) mx[i][j][k]=max(mx[i][j+1][k],f[1][i-1][j+1][k]); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) for(int k=j;k<=n;k++) f[0][i][j][k]=max(mx[i][j][k],f[0][i-1][j][k])+calc(i,j,k); mxx=f[0][0][0][0]; memset(f[1],~0x3f,sizeof(f[1])); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) for(int k=j+2;k<=n;k++) f[1][i][j][k]=mxx+calc(i,j,k); for(int j=1;j<=n;j++) for(int k=j;k<=n;k++) mxx=max(mxx,f[0][i-1][j][k]); } memset(f[0],~0x3f,sizeof(f[0])); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) for(int k=j+2;k<=n;k++) f[0][i][j][k]=max(f[0][i-1][j][k],f[1][i-1][j][k])+calc(i,j,k)-calc(i,j+1,k-1); memset(f[1],~0x3f,sizeof(f[1])); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) for(int k=j+2;k<=n;k++) f[1][i][j][k]=f[0][i-1][j][k]+calc(i,j,k); mxx=f[0][0][0][0]; memset(f[0],~0x3f,sizeof(f[0])); for(int i=1;i<=m;i++) { for(int j=1;j<=n;j++) for(int k=j+2;k<=n;k++) f[0][i][j][k]=max(mxx,f[0][i-1][j][k])+calc(i,j,k)-calc(i,j+1,k-1); for(int j=1;j<=n;j++) for(int k=j;k<=n;k++) mxx=max(mxx,f[1][i-1][j][k]); } memset(f[1],~0x3f,sizeof(f[1])); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) for(int k=j+2;k<=n;k++) f[1][i][j][k]=max(f[1][i-1][j][k],f[0][i-1][j][k])+calc(i,j,k); ans=f[0][0][0][0]; memset(f[0],~0x3f,sizeof(f[0])); for(int i=1;i<=m;i++) for(int j=1;j<=n;j++) for(int k=j+2;k<=n;k++) { f[0][i][j][k]=max(f[0][i-1][j][k],f[1][i-1][j][k])+calc(i,j,k)-calc(i,j+1,k-1); ans=max(ans,f[0][i][j][k]); } printf("%d\n",ans); return 0; }