学海泛舟

51nod 1158 全是1的最大子矩阵 题解

发表于 | 分类于 |

原题

传送门

题目大意

给一个矩阵，这个矩阵中的每个元素不是1就是0，问在这个矩阵中元素全是1的子矩阵的最大面积。

分析

首先，预处理每个元素向左有多少个1，这样的话，就得到了一个新的数组，不妨记为a[i][j]，通过这个数组可以快速查找以该列为右边界的最大矩形面积了。
对于每个元素（可以成为基准元素），我们以它所在列为右边界，通过a数组，知道它左边有多少个1，就以这个作为矩形的宽，那么就只要寻找上下边界就可以了，因为要构成矩形，所以，沿着右边界上下寻找，要求找到元素的a值要大于基准元素，因为只有这样才能保证矩形的完整。
通过上面的方法，只要枚举每个元素，这个问题就解决了。（在寻找上下边界时，要充分利用已经计算过的值，加快寻找，具体看代码）

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<stdio.h>
#include<vector>
#include<map>
using namespace std;
int a[505][505];
int U[505],D[505];
int main(){
	int n,m;
	scanf("%d %d",&n,&m);
	memset(a,0,sizeof a);
	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][j-1]+1;
            }
        }
	}
	int ans=0;
	for(int j=1;j<=m;++j){
        //j就是矩形的右边界
        for(int i=1;i<=n;++i){
            int tmp=i-1;
            //向上寻找对于这个i的上边界
            while(tmp&&a[i][j]<=a[tmp][j]) tmp=U[tmp];//加速过程
            U[i]=tmp;
        }
        for(int i=n;i>0;--i){
            int tmp=i+1;
            //向下寻找对于这个i的下边界
            while(tmp!=n+1&&a[i][j]<=a[tmp][j]) tmp=D[tmp];//加速过程
            D[i]=tmp;
        }
        for(int i=1;i<=n;++i){
            ans=max(ans,(D[i]-U[i]-1)*a[i][j]);
        }
	}
	printf("%d\n",ans);
	return 0;
}