当前位置：首页 > news >正文

POJ - 3494 Largest Submatrix of All 1’s（单调栈+降维）

news 来源：原创 2024/5/3 15:53:40

传送门

这题开始知道是用单调栈做，然后我一开始想的是先求出每个 $1$ 最右边最后一个 $1$ 也就是第一个小于它的数；同理求出最下面的第一个小于它的数。这样我们枚举每一个 $1$ 作为矩形的左上角然后想办法求出每行的最小的，然后每行的每个位置上下最小的似乎又要用单调栈做，这也太麻烦了，没有心思写下去了想去看看正解

实际上是化二维为一维，对于某一行或者某一列来说，我们完全可以看做它下面连续的一块 $1$ 累加而来形成一个高度，这样问题就变成了这种一维的高度求某块的最大矩形区域的问题：
在这里插入图片描述
因此我们将每列从上到下累加，然后枚举每一行，接着分别从右向左以及从左向右找到该位置数作为区间最小值的左界和右界，这样每次更新答案即可

#include <math.h>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define lowbit(x) (x&(-x))
#define mkp(x,y) make_pair(x,y)
#define mem(a,x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
const double eps=1e-8;
const double pi=acos(-1.0);
const int inf=0x3f3f3f3f;
const double dinf=1e300;
const ll INF=1e18;
const int Mod=1e9+7;
const int maxn=2020;

int a[maxn][maxn];
int st[maxn],R[maxn];
int n,m;

int main(){
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    //ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    while(~scanf("%d%d",&n,&m)){
        memset(a,0,sizeof a);
        for(int i=1,x;i<=n;i++){
            for(int j=1;j<=m;j++){
                scanf("%d",&x);
                if(x) a[i][j]=a[i-1][j]+1;
            }
            a[i][0]=a[i][m+1]=-inf;
        }
        int head,l,ans=0;
        for(int i=1;i<=n;i++){
            head=0;
            st[head++]=m+1;
            for(int j=m;j>=1;j--){
                while(a[i][st[head-1]]>=a[i][j]) head--;
                R[j]=st[head-1]-1;
                st[head++]=j;
            }
            head=0;
            st[head++]=0;
            for(int j=1;j<=m;j++){
                while(a[i][st[head-1]]>=a[i][j]) head--;
                l=st[head-1]+1;
                ans=max(ans,a[i][j]*(R[j]-l+1));
                st[head++]=j;
            }
        }
        printf("%d\n",ans);
    }

    return 0;
}