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

绝地灬酷狼 2021-10-18 08:32 192阅读 0赞

## 题意：给定一个包含0和1的矩阵，输出矩形内都是1的第二大的矩形的大小。 ##

## 分析：经典题变形而来，详见[https://www.cnblogs.com/linkstar/p/6139668.html][https_www.cnblogs.com_linkstar_p_6139668.html]，dp和单调栈两种解法，对着代码跑一遍更好理解。dp更好理解，复杂度略高。注意第二大不一定是用求最大的方法找到的第二大，也可能是最大的减去一行或者一列的大小。 ##

## dp代码： ##

#include<bits/stdc++.h>
    using namespace std;
    const int N = 1e3+5;
    int dp[N][N];
    int n,m,sum=-1,ans=-1;
    
    int main()
    {
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%1d",&dp[i][j]);
                dp[i][j]+=dp[i-1][j]*dp[i][j];
            }
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                int len=dp[i][j],dep=1;
                while(len)
                {
                    int area=len*dep;
                    if(area>ans)
                    {
                        sum=ans;ans=area;
                    }
                    else if(area>sum)
                    {
                        sum=area;
                    }
                    len=min(len,dp[i][j-dep]);
                    dep++;
                }
            }
        }
        if(sum==-1) sum=0;
        printf("%d\n",sum);
        return 0;
    }

## 单调栈代码： ##

[https_www.cnblogs.com_linkstar_p_6139668.html]: https://www.cnblogs.com/linkstar/p/6139668.html