51Nod 1158 全是1的最大子矩阵 —— 预处理 + 暴力枚举 or 单调栈

题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1158

1158 全是1的最大子矩阵

基准时间限制：1 秒空间限制：131072 KB 分值: 80 难度：5级算法题

关注

给出1个M*N的矩阵M1，里面的元素只有0或1，找出M1的一个子矩阵M2，M2中的元素只有1，并且M2的面积是最大的。输出M2的面积。

Input

第1行:2个数m,n中间用空格分隔(2 <= m,n <= 500)
第2 - N + 1行：每行m个数，中间用空格分隔，均为0或1。

Output

输出最大全是1的子矩阵的面积。

Input示例

Output示例

题解：

POJ2559 加强版，预处理一下以每个格子作为底，最多可以往上延伸多少个格子，这样就可以把这些连续的格子看成一根柱子，如果按行枚举，那么就转化成了POJ2559的问题了，即利用单调栈，当然这题也可以直接暴力枚举。

暴力枚举：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 2e9;
15 const LL LNF = 9e18;
16 const int MOD = 1e9+7;
17 const int MAXM = 1e5+10;
18 const int MAXN = 5e2+10;
19 
20 int a[MAXN][MAXN];
21 int main()
22 {
23     int n, m;
24     while(scanf("%d%d",&m,&n)!=EOF)
25     {
26         for(int i = 1; i<=n; i++)
27         for(int j = 1; j<=m; j++)
28         {
29             scanf("%d",&a[i][j]);
30             if(a[i][j]) a[i][j] += a[i-1][j];
31         }
32 
33         int ans = 0;
34         for(int i = 1; i<=n; i++)
35         for(int j = 1; j<=m; j++)
36         {
37             int w = a[i][j];
38             ans = max(ans, w*1);
39             for(int k = j+1; k<=m; k++)
40             {
41                 w = min(w,a[i][k]);
42                 ans = max(ans, w*(k-j+1));
43             }
44         }
45         printf("%d
", ans);
46     }
47 }

View Code

单调栈：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 2e9;
15 const LL LNF = 9e18;
16 const int MOD = 1e9+7;
17 const int MAXM = 1e5+10;
18 const int MAXN = 5e2+10;
19 
20 int h[MAXN][MAXN];
21 int Stack[MAXN][2], top;
22 int main()
23 {
24     int n, m;
25     while(scanf("%d%d",&m,&n)!=EOF)
26     {
27         for(int i = 1; i<=n; i++)
28         for(int j = 1; j<=m; j++)
29         {
30             scanf("%d",&h[i][j]);
31             if(h[i][j]) h[i][j] += h[i-1][j];   //预处理出高度，这样就可转化为POJ2559了
32         }
33 
34         int ans = 0;
35         for(int i = 1; i<=n; i++)
36         {
37             top = 0;
38             h[i][m+1] = -1;     //在最后加个很小的值，就能把栈里的元素全部倒出来了
39             for(int j = 1; j<=m+1; j++)
40             {
41                 int len = 0;    //长度
42                 while(top && Stack[top-1][0]>=h[i][j])  //如果当前高度小于等于
43                 {
44                     len += Stack[top-1][1];     //长度累加
45                     ans = max(ans,Stack[top-1][0]*len);
46                     top--;
47                 }
48                 Stack[top][0] = h[i][j];    //当前元素入栈
49                 Stack[top++][1] = len+1;    //把出栈了的元素的长度都累加到入栈元素当中去
50             }
51         }
52 
53         printf("%d
", ans);
54     }
55 }

View Code