2019牛客全国多校第八场A题 All-one Matrices（单调栈）

题意：让你找最大不可扩展全1子矩阵的数量；

题解：考虑枚举每一行为全1子矩阵的的底，然后从左到右枚举；up[i][j]:表示（i,j）这个位置向上可扩展多少，同时还有记录每个位置(i,j)向左最多可扩展到哪个位置pos;

用单调栈维护一个递增的{up[i][j]，pos},如果当st.top.first>up[i][j]时，表示栈顶的元素最右可扩展到j-1;

lzero:表示下一行最右0所在位置，如果st.top.second<=lzero则表示该栈顶所表示矩阵不可再往下扩展，则对答案贡献1；

参考代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define mkp make_pair
const int maxn=3010;
char s[maxn];
int n,m,ans,up[maxn][maxn],num[maxn][maxn];
stack<pii> st;

int main()
{
    scanf("%d%d",&n,&m);
    ans=0;
     for(int i=1;i<=n;++i)
    {
        scanf("%s",s+1);
        for(int j=1;j<=m;++j)
        {
            if((num[i][j]=s[j]-'0')) up[i][j]=up[i-1][j]+1;
            else up[i][j]=0;
        }
    }
    for(int i=1;i<=n;++i)
    {
        int lzero=-1;
        while(!st.empty()) st.pop();
        for(int j=1;j<=m+1;++j)
        {
            int pos=j;
            while(!st.empty()&&st.top().first>up[i][j])
            {
                if(st.top().second<=lzero) ans++;
                pos=st.top().second;
                st.pop();
            }
            if(!num[i+1][j]) lzero=j;
            if(st.empty()||st.top().first<up[i][j])
                st.push(mkp(up[i][j],pos));
        }
    }
    printf("%d
",ans);

    return 0;
}