经典单调栈最大子矩形——牛客多校第二场H

痛定思痛。 2023-10-11 09:10 17阅读 0赞

题目是求次大子矩形，那么在求最大子矩形的时候维护M1，M2即可

转移M2时比较的过程要注意一下

#include<bits/stdc++.h>
    using namespace std;
    #define maxn 1005
    char mp[maxn][maxn];
    int n,m,f[maxn][maxn],M1,M2;
    
    int stk[maxn],top,w[maxn];
    void calc(int i){
        top=0;
        f[i][m+1]=0;
        memset(w,0,sizeof w);
        for(int j=1;j<=m+1;j++)
            if(f[i][j]>stk[top]){
                stk[++top]=f[i][j];
                w[top]=1;
            }     
            else {
                int width=0;
                while(f[i][j]<stk[top]){
                    width+=w[top];
                    
                    if(stk[top]*(width)>=M1){
                        M2=max(M1,stk[top]*(width-1));//这里的用M1和高度*（宽度-1）相比较，大的更优
                        M1=stk[top]*(width);
                    }
                    else
                        M2=max(M2,stk[top]*width);
                        
                    top--;
                }
                stk[++top]=f[i][j],w[top]=width+1;
            }
    } 
    
    int main(){
        cin>>n>>m;
        for(int i=1;i<=n;i++)scanf("%s",mp[i]+1);
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++)
                if(mp[i][j]=='1')
                    f[i][j]=f[i-1][j]+1;
                else f[i][j]=0;
        }
        for(int i=1;i<=n;i++)
            calc(i);
        cout<<M2<<endl;
    }

转载于:https://www.cnblogs.com/zsben991126/p/11286257.html

发表评论取消回复

表情：

评论列表（有 0 条评论，17人围观）

还没有评论，来说两句吧...

相关阅读

相关 poj2559（单调栈）最大矩形面积

![Center][] //单调栈 //思路很好的 include<cstdio> include<iostream> using

淡淡的烟草味﹌/ 2024年02月18日 14:06/ 0 赞/ 44 阅读

相关单调栈(最大子矩形强化版)——牛客多校第八场A

求01矩阵里有多少个不同的1矩阵首先预处理出pre\[i\]\[j\]表示i上面连续的1个数，对每行的高度进行单调栈处理栈里的元素维护两个值：pre\[i\]\[j\]

川长思鸟来/ 2023年10月11日 09:14/ 0 赞/ 9 阅读

相关数位dp——牛客多校H

/ x[1,A] y[1,B] x^y<C 或 x&y>C 把ABC拆成二进制后按位进行数位dp dp[pos][s1][s2][f1][f2] 表示从高到低第pos位

电玩女神/ 2023年10月11日 09:14/ 0 赞/ 19 阅读

相关经典单调栈最大子矩形——牛客多校第二场H

题目是求次大子矩形，那么在求最大子矩形的时候维护M1，M2即可转移M2时比较的过程要注意一下 include<bits/stdc++.h> using n

痛定思痛。/ 2023年10月11日 09:10/ 0 赞/ 18 阅读

相关 LeetCode_单调栈_困难_85.最大矩形

目录 1.题目 2.思路 3.代码实现（Java） 1.题目给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找

r囧r小猫/ 2023年10月06日 19:11/ 0 赞/ 46 阅读

相关 2019牛客多校第三场F Planting Trees（单调队列）题解

题意：求最大矩阵面积，要求矩阵内数字满足\\(max - min < m\\) 思路：枚举上下长度，在枚举的时候可以求出每一列的最大最小值\\(cmax，cm

た入场券/ 2021年11月05日 02:06/ 0 赞/ 282 阅读

相关 2019牛客暑期多校训练营（第八场）A-All-one Matrices（单调栈+思维）

[>传送门<][Link 1] 题意：给你一个01矩阵，求出所有不可扩大的全为1的矩阵的个数思路：比赛的时候想到了用单调栈，但是也只是想到了，并不知道怎么用，其实和之前求

痛定思痛。/ 2021年10月29日 12:48/ 0 赞/ 171 阅读

相关牛客多校第六场记录

A 题意: 垃圾分类思路: 模拟 include <cstdio> include <iostream> include <algorithm>

柔光的暖阳◎/ 2021年10月29日 12:20/ 0 赞/ 263 阅读

相关 2019牛客暑期多校训练营（第二场）H：Second Large Rectangle（dp or 单调栈）

题意：给定一个包含0和1的矩阵，输出矩形内都是1的第二大的矩形的大小。分析：经典题变形而来，详见[https://www.cnblogs.com/linkstar/p

绝地灬酷狼/ 2021年10月18日 08:32/ 0 赞/ 213 阅读

相关 2019牛客多校第二场 Kth Minimum Clique

题目描述 Given a vertex-weighted graph with N vertices, find out the K-th minimum weight

淡淡的烟草味﹌/ 2021年10月18日 07:28/ 0 赞/ 274 阅读