【题解】51nod 1158 全是1的最大子矩阵_综合

题目传送门
题意：
给出 $1$ 个 $n\times m$ 的矩阵 $M_1$ ，里面的元素只有 $0$ 或 $1$ ，找出 $M_1$ 的一个子矩阵 $M_2$ ， $M_2$ 中的元素只有1，并且 $M_2$ 的面积是最大的。输出 $M_2$ 的面积。

这道题，是一道十分玄学的题目。
在题目上方有两个标签——“单调栈”和“DP”。但实际上，这道题根本就不需要单调栈或是DP。
~~因为我不会，所以我只会玄学~~
首先，我们随便拿一组数据（样例）：

1 1 0
1 1 1
0 1 1

我们把每一个1上方的连续的1的数量写一下：

1 1 0
2 2 1
0 3 2

那么好了，我们一行行来。首先看第一行，在第一行及其上方（其实也就是第一行）的最大全1矩形面积为2，第二行及其上方的最大全1矩阵面积为4，第三行及其上方的最大全1矩阵面积同样为4。所以整个矩阵的最大全1矩阵面积为4。
这个面积的求法，对于该行每一个连续的非0段，统计它的长度和最小值（也就是高度），求出面积，取所有段的最大值即可。
想到这里的我，愉快的写了一份代码，交了上去。
提交链接1

#include<bits/stdc++.h>
using namespace std;
int a[505][505];
int main()
{
    int n,m,ans=0;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
    scanf("%d",&a[i][j]);if(a[i][j]==1) a[i][j]=a[i-1][j]+1;//统计在这个点上面连续的1的数量（包括它自己）}for(int i=1;i<=n;i++){
    int nowlen=0,maxlen=0,nowhig=1<<30,maxhig=0;//nowlen当前段长度，nowhig当前段最小值（高度），maxlen和maxhig是面积最大的段的长度和高度for(int j=1;j<=n;j++){
    if(!a[i][j]&&a[i][j-1])//每一个段结束后把当前段的长度和高度清零{
    nowlen=0;nowhig=1<<30;}if(a[i][j]){
    nowlen++;nowhig=min(nowhig,a[i][j]);if(nowlen*nowhig>maxlen*maxhig)//实时更新面积{
    maxlen=nowlen;maxhig=nowhig;}}}ans=max(ans,maxlen*maxhig);}printf("%d",ans);return 0;
}

然后呢？
WA 了 $6$ 个点。
我就想，这道题真的只能用单调栈或是DP吗？
于是，我下了一组数据。

正解是 $6$ ，也就是右上角长为 $2$ ，高为 $3$ 的矩形。但我的程序输出了 $5$ 。看到第三行，原来在计算第三行第三到五个数组成的段时，第三个数的值为 $1$ ，所以，后面的高度就被锁定成了 $1$ ，而忽略了后面 $3$ 的高度。
怎么办？
我的原程序是从左往右扫，于是我想到了一个玄学的方法：
从左往右扫，再从右往左扫
想到这里的我，愉快的写了一份代码，交了上去。
提交链接2

#include<bits/stdc++.h>
using namespace std;
int a[505][505];
int main()
{
    int n,m,ans=0;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
    scanf("%d",&a[i][j]);if(a[i][j]==1) a[i][j]=a[i-1][j]+1;}for(int i=1;i<=n;i++){
    int nowlen=0,maxlen=0,nowhig=1<<30,maxhig=0;for(int j=1;j<=n;j++){
    if(!a[i][j]&&a[i][j-1]){
    nowlen=0;nowhig=1<<30;}if(a[i][j]){
    nowlen++;nowhig=min(nowhig,a[i][j]);if(nowlen*nowhig>maxlen*maxhig){
    maxlen=nowlen;maxhig=nowhig;}}}ans=max(ans,maxlen*maxhig);//从右往左扫nowlen=0,maxlen=0,nowhig=1<<30,maxhig=0;for(int j=n;j>=1;j--){
    if(!a[i][j]&&a[i][j+1]){
    nowlen=0;nowhig=1<<30;}if(a[i][j]){
    nowlen++;nowhig=min(nowhig,a[i][j]);if(nowlen*nowhig>maxlen*maxhig){
    maxlen=nowlen;maxhig=nowhig;}}}ans=max(ans,maxlen*maxhig);}printf("%d",ans);return 0;
}

然后呢？
WA 了 $1$ 个点：# $7$ 。
其实这个结果，在我交之前，早就已经想到了。我还知道它们会出什么样的数据来卡我这个程序。例如

在最后一行，不管你是从左往右扫，还是从右往左扫，都会在第一个数字锁死高度，因为它是对称的。
于是，我又想到了一个更加玄学的方法：
先从上往下扫，再从下往上扫。
这样就可以完美处理这个毒瘤数据。
想到这里的我，愉快的写了一份代码，交了上去。
提交链接3

#include<bits/stdc++.h>
using namespace std;
int a[505][505];
int main()
{
    int n,m,ans=0;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++)for(int j=1;j<=m;j++){
    scanf("%d",&a[i][j]);if(a[i][j]==1)a[i][j]=a[i-1][j]+1;}for(int i=1;i<=n;i++){
    int nowlen=0,maxlen=0,nowhig=1<<30,maxhig=0;for(int j=1;j<=n;j++){
    if(!a[i][j]&&a[i][j-1]){
    nowlen=0;nowhig=1<<30;}if(a[i][j]){
    nowlen++;nowhig=min(nowhig,a[i][j]);if(nowlen*nowhig>maxlen*maxhig){
    maxlen=nowlen;maxhig=nowhig;}}}ans=max(ans,maxlen*maxhig);nowlen=0,maxlen=0,nowhig=1<<30,maxhig=0;for(int j=n;j>=1;j--){
    if(!a[i][j]&&a[i][j+1]){
    nowlen=0;nowhig=1<<30;}if(a[i][j]){
    nowlen++;nowhig=min(nowhig,a[i][j]);if(nowlen*nowhig>maxlen*maxhig){
    maxlen=nowlen;maxhig=nowhig;}}}ans=max(ans,maxlen*maxhig);}//还原矩阵for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j])a[i][j]=1;//矩阵翻转for(int i=1;i<=n/2;i++)for(int j=1;j<=m;j++)swap(a[i][j],a[n-i+1][j]);//计算其上连续1个数for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(a[i][j])a[i][j]=a[i-1][j]+1;//反着扫for(int i=1;i<=n;i++){
    int nowlen=0,maxlen=0,nowhig=1<<30,maxhig=0;for(int j=1;j<=n;j++){
    if(!a[i][j]&&a[i][j-1]){
    nowlen=0;nowhig=1<<30;}if(a[i][j]){
    nowlen++;nowhig=min(nowhig,a[i][j]);if(nowlen*nowhig>maxlen*maxhig){
    maxlen=nowlen;maxhig=nowhig;}}}ans=max(ans,maxlen*maxhig);nowlen=0,maxlen=0,nowhig=1<<30,maxhig=0;for(int j=n;j>=1;j--){
    if(!a[i][j]&&a[i][j+1]){
    nowlen=0;nowhig=1<<30;}if(a[i][j]){
    nowlen++;nowhig=min(nowhig,a[i][j]);if(nowlen*nowhig>maxlen*maxhig){
    maxlen=nowlen;maxhig=nowhig;}}}ans=max(ans,maxlen*maxhig);}printf("%d",ans);return 0;
}

然后呢？
震惊！！！
这个 $114$ 行（含注释 $118$ 行）的代码成功的 AC 了！！！
~~要什么单调栈呀，要什么DP呀，上下左右各扫几遍就行了。~~

对于这个算法的时间复杂度，输入需要 $O (n m)$ ，从上往下扫需要 $O (2 n ?)$ ，还原矩阵需要 $O (n m)$ ，翻转矩阵需要 $O(\frac{nm}{2})$ ，重新计算需要 $O (n m)$ ，从下往上扫需要 $O (2 n ?)$ ，由于n和m是同一个数量级的，所以总时间复杂度为 $O (n m)$ ，可能常数会比较大（因为上下左右都在扫），但对于500的数据来说，已经完全足够了。

by 232323 in 51nod

参考文献：
51nod 1158 全是1的最大子矩阵 (单调栈) 详细图解

勘误：

当你们看我的代码时，是不是感觉有点不太对劲？
一个 $n\times m$ 的矩阵，枚举每一个点， $i$ 是从 $1$ 到 $n$ ， $j$ 又是从 $1$ 到 $n$ 。
自己改吧。~~（居然还 AC 了，不可思议）~~
既然都已经发现了勘误 $1$ ，那么在时间复杂度的分析里，从上往下扫和从下往上扫的时间复杂度都应该是 $O (2 n m)$ ，对总时间复杂度无伤大雅，但毕竟还是要严谨的。