蓝桥集训之矩形牛棚

蓝桥集训之矩形牛棚

• 核心思想：单调队列

  • 模板：Acwing.131.直方图矩形面积
  • 首先遍历所有下界 然后确定以该下界为底的直方图 求最大矩形
    • 

•   #include <iostream>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    const int N = 3010;
    
    int stk[N],top;
    int r[N],l[N];
    int g[N][N],h[N][N];
    int n,m,q;
    
    int work(int h[])  //找最大面积
    {
        top = 0;
        stk[++top] = 0;  //边界下标加入
        h[0] = h[m+1] = -1;  //左右边界
        for (int i = 1; i <= m; i ++ )
        {
            while (h[stk[top]] >= h[i]) top -- ;  //h[i]更优
            l[i] = stk[top];  //l[i]为左边第一个比h[i]小的
            stk[ ++ top] = i;
        }
        top = 0;
        stk[++top] = m+1;  //右边界下标
        for (int i = m; i; i -- )
        {
            while (h[stk[top]] >= h[i]) top -- ;
            r[i] = stk[top];  //r[i]为右边第一个比h[i]小的
            stk[ ++ top] = i;
        }
        
        int res=0;
        for(int i=1;i<=m;i++)
            res = max(res,h[i] * (r[i] - l[i] - 1));  //长乘宽
        return res;
    }
    int main()
    {
        cin>>n>>m>>q;
        while(q--)
        {
            int x,y;
            cin>>x>>y;
            g[x][y] = 1;
        }
        
        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ )
                if(!g[i][j])  //如果没有被破坏
                    h[i][j] = h[i-1][j] + 1;  //递归求h数组
                    
        int res=0;
        for (int i = 1; i <=n; i ++ )
            res = max(res , work(h[i]));
            
        cout<<res<<endl;
    }