链接：https://www.nowcoder.com/acm/contest/131/B
来源：牛客网
第一行输入五个整数 R，C，X，Y，Z。
1 ≤ X ≤ R.
1 ≤ Y ≤ C.
1 ≤ Z ≤ R x C.
|Mij|<=1e9
输出满足以上条件的最大子矩阵和。
考虑枚举行数。
枚举行数后枚举从哪行开始。
预处理出来纵向前缀和，然后枚举的时候就把每一个元素转化成柱形图那样的格式，然后求最大值就好了。
求最大值时的思想是枚举最后一个元素，然后看前面的元素，前面元素大于0直接放，小于0的就把队尾取出来，加到这个元素，直到不小于0或者队列为空位置。
以数结尾的最大值是目前队列元素里面的和。
用单调栈也可以做。
#include<cstdio> #include<cstring> #include<vector> #include<algorithm> using namespace std; const int N=508; int q[N],p[N],zt[N][N],L[N]; long long mp[N][N],up[N][N],a[N]; int R,C,X,Y,Z; long long work(){ for(int i=1;i<=C;++i) p[i]=i; int h=1,r=0; long long ans=0,sum=0; q[1]=0; for(int i=1;i<=C;++i) { while(h<=r&&p[q[h]]<=i-Y) sum-=a[q[h++]]; while(h<=r&&a[i]<0) { sum-=a[q[r]]; a[i]+=a[q[r]]; p[i]=p[q[r--]]; } if(a[i]>0) sum+=a[i],q[++r]=i; while(h<=r&&(L[i]-L[p[q[h]]]>Z)) sum-=a[q[h++]]; ans=max(ans,sum); } return ans; } int main(){ long long ans=0; scanf("%d%d%d%d%d",&R,&C,&X,&Y,&Z); for(int i=1;i<=R;++i) for(int j=1;j<=C;++j) scanf("%lld",&mp[i][j]); for(int i=1;i<=R;++i) for(int j=1;j<=C;++j) up[i][j]=up[i-1][j]+mp[i][j],zt[i][j]=zt[i-1][j]+(mp[i][j]==0); for(int len=1;len<=X;++len){ for(int i=1;i<=R-len+1;++i){ for(int j=1;j<=C;++j) a[j]=up[i+len-1][j]-up[i-1][j],L[j]=zt[i+len-1][j]-zt[i-1][j]; for(int j=2;j<=C;++j) L[j]+=L[j-1]; ans=max(ans,work()); } } printf("%lld\n",ans); }
原文：https://www.cnblogs.com/mfys/p/9278152.html