51nod1158 最大子矩形 单调栈应用

#include<iostream> #include<cstring> #include<cstdio> using namespace std; int mp[600][600],m,n,ans; void work(int i){//以第i行为底的矩阵 int stk[600],w[600]={},h[600]={},top=0;//高度栈，左宽栈 memset(stk,-1,sizeof stk); for(int j=1;j<=m;j++)h[j]=mp[i][j]; for(int j=1;j<=m;j++){ if(h[j]>stk[top]) stk[++top]=h[j],w[top]=1; else { int cnt=0; while(top>=1 && stk[top]>=h[j]){ ans=max(ans,stk[top]*(w[top]+cnt)); cnt+=w[top--]; } stk[++top]=h[j]; w[top]=cnt+1; } } } int main(){ while(scanf("%d%d",&n,&m)==2){ memset(mp,0,sizeof mp); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&mp[i][j]); m++;//在最右边添一个全0列 for(int j=1;j<=m;j++) for(int i=1;i<=n;i++) if(mp[i][j]==1)mp[i][j]=mp[i-1][j]+1; ans=0; for(int i=1;i<=n;i++) work(i); printf("%d\n",ans); } }

 

转载于:https://www.cnblogs.com/zsben991126/p/10329715.html