题目描述
Description
Hzgd神牛准备给自己盖一座很华丽的宫殿。于是,他看中了一块N*M的矩形空地。空地中每个格子都有自己的海拔高度。胡张想让他的宫殿的平均海拔在海平面之上(假设海平面的高度是0,平均数都会算吧?)。而且,胡张希望他的宫殿是个矩形且尽量大,能够容纳更多的人来膜拜他。请问胡张的宫殿最后会有多大?
Input Format
第一行为N和M。之后N行,每行M个数,描述的空地的海拔。
Output Format
输出一行,表示宫殿最大面积。
Sample Input
3 2
4 0
-10 8
-2 -2
Sample Output
4
Data Limit
对于30%的数据,N,M≤50;
对于100%的数据,N,M≤200;
题解
dp+单调栈。
这道题很像最大子矩阵。但是是求面积大于0的最大子矩阵。我们考虑像普通求法一样枚举左右边界,用前缀和表示1~i行的总和。后面画图可知单调栈的操作。
#include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<cmath> #include<algorithm> #define ll long long using namespace std; int n,m,ans,f[202],top; ll area,sum[202][202],stack[202]; void init() { scanf("%d%d",&n,&m); int i,j,x; for(i=1;i<=n;i++) for(j=1;j<=m;j++) {scanf("%d",&x); sum[i][j]=sum[i][j-1]+x; } } int erf(ll x) { int l=1,r=top,mid,w=-1; while(l<=r) {mid=(l+r)>>1; if(stack[mid]<x) {w=mid; r=mid-1;} else l=mid+1; } return w; } void dp() { int i,j,k,w; ll a; for(i=1;i<=m;i++) for(j=i;j<=m;j++) {area=0; stack[0]=1e10; top=0; for(k=1;k<=n;k++) {a=sum[k][j]-sum[k][i-1]; area+=a; if(area>0) ans=max(ans,k*(j-i+1)); else {w=erf(area); if(w!=-1) ans=max(ans,(k-f[w])*(j-i+1)); } if(area<stack[top]) {stack[++top]=area; f[top]=k; } } } printf("%d\n",ans); } int main() { init(); dp(); return 0; }