全是1的最大子矩阵问题

　　前一次寒假排位赛中遇到了这个问题，后来思考了一下。写个类似问题的总结。

　　这题的模型可以在51nod中找到：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1158。但是其问题规模比较小，n^3暴力似乎都可以。

　　正解应当是单调栈，我记得上次在《挑战程序设计2》里面看到过这题，可以用单调栈在O(n*m)的复杂度下求解。虽然思路比较简单，但是我自己写起来还是花了比较久的时间= =。代码能力真的弱。。想说下的是，这题下如果规模是5000*5000，那么a数组和h数组应当只使用一个即可，或者a数组变成char或bool数组，否则是会超内存的。int一个5000*5000的就需要100M了。单调栈的代码如下：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <stack>
 5 using namespace std;
 6 const int N = 500 + 5;
 7 
 8 int n,m;
 9 int a[N][N];
10 int h[N][N];
11 int left[N];
12 
13 int main()
14 {
15     while(scanf("%d%d",&n,&m) == 2)
16     {
17         memset(h,0,sizeof h);
18         for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
19         for(int i=1;i<=n;i++)
20         {
21             for(int j=1;j<=m;j++)
22             {
23                 if(a[i][j] == 1) h[i][j] = h[i-1][j] + 1;
24                 else h[i][j] = 0;
25             }
26         }
27         int ans = 0;
28         for(int i=1;i<=n;i++)
29         {
30             int pos = 0;
31             stack<int> S;
32             h[i][m+1] = 0;
33             //memset(left,0,sizeof left);
34             for(int j=1;j<=m+1;j++)
35             {
36                 int now = h[i][j];
37                 if(S.empty() || h[i][S.top()] < now)
38                 {
39                     if(now == 0) pos = j;
40                     else
41                     {
42                         S.push(j);
43                         left[j] = j;
44                     }
45                 }
46                 else if(h[i][S.top()] == now)
47                 {
48                     left[j] = left[S.top()];
49                     S.push(j);
50                 }
51                 else
52                 {
53                     while(!S.empty() && h[i][S.top()] > now)
54                     {
55                         int x = S.top(); S.pop();
56                         ans = max(ans, (j-left[x])*h[i][x]);
57                     }
58                     if(now == 0) pos = j;
59                     else if(S.empty()) left[j] = pos + 1;
60                     else left[j] = S.top() + 1;
61                     if(now) S.push(j);
62                 }
63             }
64         }
65         printf("%d
",ans);
66     }
67     return 0;
68 }

单调栈

　　值得一提的是这里还有一种简单的方法，直接用两个数组记录，到左边的第一个比当前h小的位置，右边同样也记录一下，然后一行内枚举位置，再依次更新答案（即h[i][j]*(right[j]-left[j]-1)）即可。两个数组的记录是可以在每一行先做预处理的，复杂度为线性。那么总的时间复杂度和上面单调栈是一样的。但是这个方法更容易理解，并且好写。代码如下：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <stack>
 5 using namespace std;
 6 const int N = 500 + 5;
 7 
 8 int n,m;
 9 int a[N][N];
10 int h[N][N];
11 int left[N],right[N];
12 
13 int main()
14 {
15     while(scanf("%d%d",&n,&m) == 2)
16     {
17         memset(h,0,sizeof h);
18         for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
19         for(int i=1;i<=n;i++)
20         {
21             for(int j=1;j<=m;j++)
22             {
23                 if(a[i][j] == 1) h[i][j] = h[i-1][j] + 1;
24                 else h[i][j] = 0;
25             }
26         }
27         int ans = 0;
28         for(int i=1;i<=n;i++)
29         {
30             for(int j=1;j<=m;j++)
31             {
32                 int now = j - 1;
33                 for(;now && h[i][j] <= h[i][now];now=left[now]);
34                 left[j] = now;
35             }
36             for(int j=m;j>=1;j--)
37             {
38                 int now = j + 1;
39                 for(;now != m+1 && h[i][j] <= h[i][now];now=right[now]);
40                 right[j] = now;
41             }
42             for(int j=1;j<=m;j++) ans = max(ans, (right[j]-left[j]-1)*h[i][j]);
43         }
44         printf("%d
",ans);
45     }
46     return 0;
47 }

方法2

　　再提供一个类似的题目：SPOJ-MINSUB。题意是求一个面积大于等于k的子矩阵，这个矩阵内的最小的元素最大。做法是二分答案，然后原矩阵内值小于这个答案的置0，否则置1。再用同样的方法DP即可。代码如下：

 1 #include <stdio.h>
 2 #include <algorithm>
 3 #include <string.h>
 4 #include <stack>
 5 using namespace std;
 6 const int N = 1000 + 5;
 7 
 8 int n,m;
 9 int a[N][N];
10 int h[N][N];
11 int left[N];
12 int area,k;
13 bool solve(int mid)
14 {
15     for(int i=1;i<=n;i++)
16     {
17         for(int j=1;j<=m;j++)
18         {
19             if(a[i][j] >= mid) h[i][j] = h[i-1][j] + 1;
20             else h[i][j] = 0;
21         }
22     }
23     int ans = 0;
24     for(int i=1;i<=n;i++)
25     {
26         int pos = 0;
27         stack<int> S;
28         h[i][m+1] = 0;
29         for(int j=1;j<=m+1;j++)
30         {
31             int now = h[i][j];
32             if(S.empty() || h[i][S.top()] < now)
33             {
34                 if(now == 0) pos = j;
35                 else
36                 {
37                     S.push(j);
38                     left[j] = j;
39                 }
40             }
41             else if(h[i][S.top()] == now)
42             {
43                 left[j] = left[S.top()];
44                 S.push(j);
45             }
46             else
47             {
48                 while(!S.empty() && h[i][S.top()] > now)
49                 {
50                     int x = S.top(); S.pop();
51                     ans = max(ans, (j-left[x])*h[i][x]);
52                 }
53                 if(now == 0) pos = j;
54                 else if(S.empty()) left[j] = pos + 1;
55                 else left[j] = S.top() + 1;
56                 if(now) S.push(j);
57             }
58         }
59     }
60     return (area = ans) >= k;
61 }
62 
63 int main()
64 {
65     int T; scanf("%d",&T);
66     while(T--)
67     {
68         scanf("%d%d%d",&n,&m,&k);
69         int L = 1, R = 0;
70         for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {scanf("%d",&a[i][j]); R = max(R, a[i][j]);}
71         int ans = -1;
72         area = 0;
73         while(L <= R)
74         {
75             int mid = L + R >> 1;
76             if(solve(mid))
77             {
78                 ans = mid;
79                 L = mid + 1;
80             }
81             else R = mid - 1;
82         }
83         solve(ans);
84         printf("%d %d
",ans,area);
85     }
86     return 0;
87 }

View Code