今天模拟赛 B 没想出来,甚至没到单调栈那一步。到了可能也不会做。
发现单调栈已经忘干净了,之前学过的悬线法也不太会,这里补一下单调栈。
板子:HISTOGRA - Largest Rectangle in a Histogram
在我的这篇博客里有题解。总之我自己是看懂了的。
单调栈求最大全 1 子矩阵问题
思路同上,只是枚举行,对于每一行处理列最往上能扩展多少作为该位置的高度,将其转换为当前行上的上述问题。
不要忘了清空 top,以及每次需要多建一个位置处理最后栈中剩余。
#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int ans;
int a[N][N];
int top,s[N],w[N],b[N];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char c;
scanf("%s",&c);
if(c=='F') a[i][j]=1;
else a[i][j]=0;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if((a[i][j]==a[i-1][j]||i==1)&&a[i][j]) b[j]++;
else if(a[i][j]) b[j]=1;
else b[j]=0;
}
top=0;
b[m+1]=0;
for(int j=1;j<=m+1;j++){
if(b[j]>s[top]){s[++top]=b[j];w[top]=1;continue;}
int kuan=0;
while(s[top]>b[j]){
kuan+=w[top];
ans=max(ans,kuan*s[top]);
top--;
}
s[++top]=b[j];
w[top]=kuan+1;
}
}
printf("%d",ans*3);
}
标签:int,top,笔记,学习,++,ans,kuan,单调
From: https://www.cnblogs.com/Moyyer-suiy/p/17818126.html