2019牛客暑期多校训练营（第八场） A All-one Matrices(单调栈)

题目链接：https://ac.nowcoder.com/acm/contest/888#question

题目大意：求最大全1矩阵个数

题目思路：每次在高度变小的时候可以发现前面的那个矩阵没办法再继续右移了，同时高度也定了也就是不能上移了，左边的话需要用单调栈维护不能继续左移的位置，所以只用判断能不能下移就能确定这次要不要++，一直到不能下移再算就能保证不会算重。首先预处理h[i][j]表示从i,j处向上最多能延伸多少个1，sum表示一行内的前缀和。如果出现多个高度相同的矩阵，只推入最左边那个。所以栈中高度一定是递增的。当当前的高度小于栈顶高度时，说明已经不能向右延伸了，就可以进行计算答案，如果说不能向下延伸就能++，这里要注意，一定要更新左界到他最左边的地方，然后判断最左边的地方到该处的前面一位(这一位是阻拦前一个矩阵继续扩张的位所以是前面一位)下面一行是否都是1。

给两个队友提供的牛B样例，过不去就输出中间值看看哪里少了：

1.
7 8
10000001
11000011
11100111
11111111
01111110
00111100
00011000

输出16

2.

6 25
0110110101111110101001011
1001101111100100010111011
0111110111000000100000011
0101111011000100011011111
1011001111100010001111111
1100000001011010101001010

输出40

#include<bits/stdc++.h>

using namespace std;
#define inf 0x3f3f3f3f
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
const int MAXN = 3e3+5;
int n,m,h[MAXN][MAXN],sum[MAXN][MAXN];
char mp[MAXN][MAXN];
struct node{
    int pos,l;
};
stack<node>s;
int main()
{
    while(~scanf("%d%d",&n,&m)){
        memset(h,0,sizeof(h));
        memset(sum,0,sizeof(sum));
        rep(i,1,n){
            scanf("%s",mp[i]+1);
            rep(j,1,m){
                if(mp[i][j]=='1')h[i][j]=h[i-1][j]+1,sum[i][j]=sum[i][j-1]+1;
                else h[i][j]=0,sum[i][j]=sum[i][j-1];
            }
        }
        int ans=0;
        rep(i,1,n){
            while(!s.empty())s.pop();
            rep(j,1,m+1){
                node tmp={j,j};
                while(!s.empty()&&h[i][j]<h[i][s.top().pos]){
                    if(sum[i+1][j-1]-sum[i+1][s.top().l-1]!=j-s.top().l)ans++;
                    tmp.l=s.top().l;
                    s.pop();
                }
                if(s.empty()||h[i][s.top().pos]!=h[i][j])s.push(tmp);
            }
        }
        printf("%d\n",ans);
    }
    return 0;
}

以下是代码：