19牛客多校第二场 H题
首先假设这个题如果是问最大值的话，这个一个想法肯定是个单调栈的裸题了，我们碰到这个裸题的想法是先看当前的点能向上衍生的最大高度，然后根据这个高度的话我们可以操作
这个信息其实是可以n^2处理出来的，既然我们处理了最长向上衍生的，那么只需要枚举下届就ok，不需要枚举上届，枚举下届的话我们就把这道题目变成了一个简单的单调栈的模型了
那么对这个单调栈的模型该怎么操作呢，这个是个问题了，我们可以发现一点我们要的是第二大的值，这个第二大的值是从那儿产生的呢，一个是当前单调栈处理的最大值，还有一个可能当前宽度减一的最大值，这个是根据单调栈的特性得到的，我们需要牢记，然后对于这个问题，我错了好几遍 （对于这样的问题，怎么搞呢？？？？？？？？最重要的是思索本质，就是对于这个问题来说到底这些值是怎么产生的，从那儿产生的，下面是代码）
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <cmath> 6 #include <bitset> 7 #include <stack> 8 typedef long long ll; 9 using namespace std; 10 const int maxn=1100; 11 int n,m; 12 char s[maxn][maxn]; 13 int h[maxn][maxn]; 14 int ai[maxn],siz[maxn]; 15 int cnt[maxn*maxn*2]; 16 int tot=0; 17 stack<int> sta; 18 19 void solve(){ 20 ai[0]=0;ai[m+1]=0; 21 for(int i=1;i<=m;i++) siz[i]=1; 22 sta.push(0); 23 for(int i=1;i<=m+1;i++){ 24 if(ai[i]>ai[sta.top()]){ 25 sta.push(i); 26 }else{ 27 int len=0; 28 while(!sta.empty()&&ai[sta.top()]>ai[i]){ 29 len+=siz[sta.top()]; 30 cnt[++tot]=len*ai[sta.top()]; 31 if(len>1) cnt[++tot]=(len-1)*ai[sta.top()]; 32 sta.pop(); 33 } 34 sta.push(i);siz[i]=len+1; 35 } 36 } 37 } 38 39 int main(){ 40 scanf("%d%d",&n,&m); 41 for(int i=1;i<=n;i++) scanf("%s",s[i]+1); 42 for(int i=1;i<=n;i++){ 43 for(int j=1;j<=m;j++){ 44 if(s[i][j]=='0') h[i][j]=0; 45 else h[i][j]=h[i-1][j]+1; 46 } 47 } 48 49 for(int i=1;i<=n;i++){ 50 for(int j=1;j<=m;j++) ai[j]=h[i][j]; 51 solve(); 52 } 53 sort(cnt+1,cnt+tot+1); 54 if(tot<2) printf("0 "); 55 else printf("%d ",cnt[tot-1]); 56 return 0; 57 }