1158 全是1的最大子矩阵

基准时间限制：1 秒空间限制：131072 KB

给出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示例

4
思路：单调栈；
先预处理出每行中连续1的个数，然后看每列，像这样用单调栈维护当前点能扩展到的最大范围，然后面积是（R[i]-L[i]）*ans[i];
然后更新最大值；复杂度O（n*m）；

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #include<iostream>
 4 #include<string.h>
 5 #include<stdlib.h>
 6 #include<queue>
 7 #include<set>
 8 #include<vector>
 9 #include<map>
10 #include<stack>
11 using namespace std;
12 typedef long long LL;
13 typedef struct node
14 {
15         int x;
16         int id;
17 } ss;
18 stack<ss>sta;
19 int a[600][600];
20 int b[600][600];
21 int L[600];
22 int R[600];
23 int main(void)
24 {
25         int n,m;
26         while(scanf("%d %d",&n,&m)!=EOF)
27         {
28                 int i,j;
29                 for(i = 1; i <= n; i++)
30                 {
31                         for(j = 1; j <= m; j++)
32                         {
33                                 scanf("%d",&a[i][j]);
34                         }
35                 }
36                 memset(b,0,sizeof(b));
37                 for(i = 1; i <= n; i++)
38                 {
39                         for(j = 1; j <= m; j++)
40                         {
41                                 if(a[i][j])
42                                 {
43                                         b[i][j] = b[i][j-1]+1;
44                                 }
45                                 //printf("%d ",b[i][j]);
46                         }
47                 }
48                 int maxx = 0;
49                 for(j = 1; j <= m; j++)
50                 {
51                         while(!sta.empty())
52                                 sta.pop();
53                         for(i = 1; i <= n; i++)
54                         {
55                                 while(true)
56                                 {
57                                         ss ak ;
58                                         ak.x = b[i][j];
59                                         ak.id = i;
60                                         if(sta.empty())
61                                         {
62                                                 L[i] = 1;
63                                                 sta.push(ak);
64                                                 break;
65                                         }
66                                         else
67                                         {
68                                                 ss ac = sta.top();
69                                                 if(ac.x > b[i][j])
70                                                 {
71                                                         sta.pop();
72                                                         R[ac.id] = i-1;
73                                                 }
74                                                 else
75                                                 {
76                                                         L[i] = ac.id;
77                                                         sta.push(ac);
78                                                         break;
79                                                 }
80                                         }
81                                 }
82                         }
83                         while(!sta.empty())
84                         {
85                             ss al = sta.top();
86                             sta.pop();
87                             R[al.id] = n;
88                         }
89                         for(i = 1; i <= m; i++)
90                         {
91                                 int xx = R[i]-L[i]+1;
92                                 maxx = max(maxx,xx*b[i][j]);
93                         }
94                 }
95                 printf("%d
",maxx);
96         }
97         return 0;
98 }

油！油！you@