POJ3494-Largest Submatrix of All 1’s
题目链接
这是一道比较灵活的单调栈的题目，尽管我在做之前就知道它是单调栈，但还是想了很长一会儿才想到写法。
写单调栈最重要的一点就是弄清要依据什么东西单调。本题看似是求矩形面积，而且矩形与矩形之间还会分隔开，看起来貌似跟单调栈扯不上任何关系。但应该想到：若某一行的某一列出现了一个0，那么在这一列的前面行中不论出现了多少个1，都跟后续的计算无关了，所以可以把这一列已经出现过的数全视为0；出现了1的，就看它之前连续地出现过几个1，这一列的面积就是这一列出现过的1的数量了。
问题就转化成了对于每一列求类似单调栈经典题中的最大矩形了，总的复杂度为。常数非常大，有超时的风险，我TLE了一发，然后马上想到了一个剪枝：对于每一行单调栈的过程中，将0入栈其实没有实际的意义，因此在入栈时判断一下0是否需要入栈即可。加了这个剪枝就过了。
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
| #include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
int n, m;
pair<int, int> p[2005];
int main()
{
while (~scanf("%d%d", &n, &m))
{
int i, j, res = 0;
for (i = 0; i <= m; i++)
p[i].first = p[i].second = 0;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
scanf("%d", &p[j].first);
if (p[j].first)
p[j].second++;
else
p[j].second = 0;
}
stack<pair<int, int> > sta;
for (j = 1; j <= m; j++)
{
if (sta.empty() || p[j].second >= sta.top().second)
{
if (p[j].first)
sta.push(p[j]);
continue;
}
pair<int, int> t(0, 0);
while (!sta.empty())
{
if (sta.top().second < p[j].second)
break;
t.first += sta.top().first;
t.second = sta.top().second;
sta.pop();
res = max(res, t.first * t.second);
}
if (p[j].first)
{
t.first += p[j].first;
t.second = p[j].second;
sta.push(t);
}
}
pair<int, int> t(0, 0);
while (!sta.empty())
{
t.first += sta.top().first;
t.second = sta.top().second;
sta.pop();
res = max(res, t.first * t.second);
}
}
printf("%d\n", res);
}
return 0;
}
|