题意：求解第二大的矩形
题解：动态规划或单调栈，HDU1055，求解第二大的时候就需要把设x为底，y为高(x,y),(x-1,y),(x,y-1)全部用来计算一下
非要记录两个顶点上头了。。。。搞了好几个小时的map。。。然后发现记录左右边界就可以
唉。。。
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 1e3+5, INF = 0x3f3f3f3f; #define mod int(1e9+7) #define pi acos(-1.0) int n,m; int vis[maxn][maxn]; char a[maxn][maxn];int l[maxn],r[maxn]; int h[maxn][maxn]; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++){ scanf("%s",a[i]+1); } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i][j]=='1')h[i][j]=h[i-1][j]+1; else h[i][j]=0; } } ll ans1=0,ans2=0; for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); for(int j=1;j<=m;j++){ l[j]=r[j]=j; } h[i][0]=-1;h[i][m+1]=-1; l[0]=1;l[m+1]=m; for(int j=1;j<=m;j++){ while(h[i][j]<=h[i][l[j]-1]){ l[j]=l[l[j]-1]; } } for(int j=m;j>=1;j--){ while(h[i][j]<=h[i][r[j]+1]){ r[j]=r[r[j]+1]; } } for(int j=1;j<=m;j++){ if(vis[l[j]][r[j]]==0){ vis[l[j]][r[j]]=1; for(int k=0;k<=2;k++){ ll tmp; if(k==0)tmp=1ll*(r[j]-l[j]+1)*(h[i][j]); else if(k==1)tmp=1ll*(r[j]-l[j]+1-1)*h[i][j]; else tmp=1ll*(r[j]-l[j]+1)*(h[i][j]-1); //cout<<tmp<<endl; tmp=max(tmp,1ll*0); if(tmp>=ans1){ ans2=ans1;ans1=tmp; }else if(tmp>=ans2){ ans2=tmp; } } } } } cout<<ans2<<endl; }
