HihoCoder - 1673 (单调队列)
阅读原文时间:2023年07月11日阅读:2

题目:https://vjudge.net/contest/319166#problem/A

题意:有一个01矩阵,求一个最大子矩阵面积,这个矩阵要求里面都是01间隔,没有0或1连续

思路:这个题其实也就是求一个最大面积,复杂度只可以n^2,这个我们就可以想到是高楼问题,这个题唯一特殊的地方就是必须要01间隔,这个其实无所谓,我们预处理连续数组的时候改一改,因为我们每个01都可以当作一个1*1的矩阵,所以我们初值赋为1,然后再判断01交替来判断是否连续,然后我们就可以转化成高楼,我们枚举哪个为底,然后用栈计算以当前为底的所有能组成的矩形面积

#include
#define maxn 2005
#define mod 1000000007
using namespace std;
typedef long long ll;
ll n,m;
char mp[maxn][maxn];
ll d[maxn][maxn];
ll q[maxn][maxn];
void solve(){
ll mx=;
for(int i=;i<=n;i++){ stack e;
e.push();
for(int j=;j<=m+;j++){
while(q[i][j]<q[i][e.top()]){
ll dex=e.top();
e.pop();
ll r=j-e.top()-;
mx=max(mx,r*q[i][dex]);
}
e.push(j);
}
}
printf("%lld",mx);
}
int main(){
scanf("%lld%lld",&n,&m);
for(int i=;i<=n;i++){
scanf("%s",mp[i]+);
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(mp[i][j]=='') d[i][j]=;
else d[i][j]=;
}
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if((d[i][j]&&d[i-][j]==)||(d[i][j]==&&d[i-][j])) q[i][j]=q[i-][j]+;
else q[i][j]=;
}
}
solve();
return ;
}