Doubeecat's Blog

“即便前路混沌,同她走过,才算人间。”

0%

SPOJ277 CTGAME - City Game 解题报告

SP277 CTGAME - City Game

有 $k$ 片土地,每片土地被分成 $n \times m$ 个格子,每个格子里写着 R 或者 F.

对于每片土地,找一块矩形土地,要求这片土地都标着 F并且面积最大。

$n,m \leq 10^3$

解题思路

单调栈/悬线法

类似这类有障碍点找最大矩形的题显然可以用悬线法来做,不过这题里是大材小用。

其实这题是这题的变式,一时没有思路可以看下上面那题。

考虑怎么构成一个极大矩形,发现一个矩形实际上可以按照行拆分成一条一条的,比如这样。

1
2
3
4
FFF    F F F
FFF => F F F
FFF F F F
1 2 3

所以这就启发我们,对于每一个格子,可以先将其上边连续的 F 数量处理出来,记作 $h_{i,j}$,这里可以采用递推。

若 $a_{i,j} = F$ ,则 $h_{i,j} = h_{i-1,j} + 1$

否则 $h_{i,j} = 0$

我们在读入时预处理就能做到。

1
2
3
4
5
6
7
cin >> n >> m;
for (int i = 1;i <= n;++i) {
for (int j = 1;j <= m;++j) {
cin >> g[i][j];
if (g[i][j] == 'F') h[i][j] = h[i-1][j] + 1;
}
}

这样,我们就把问题拆分成了每一行上单独的这题,我们对于每一行跑一遍单调栈就解决了。

具体地说,我们现在对于一堆矩形,要求出其最大面积。我们建立两个栈,一个用来表示高度,一个用来表示宽度。从左到右扫描每个矩形:

  • 若当前矩形比栈顶矩形的高度高,直接进栈。
  • 反之,不断取出栈顶直到当前矩形比栈顶矩形的高度大。注意在出栈过程中,这些矩形也是有用的。我们考虑取他们的公共部分,也就是累加他们的宽度之和,并且用每个矩形的高度乘上累计宽度取更新答案。在这个过程结束后,我们就把当前高度与累计宽度的矩形再进栈。

整个过程结束之后,我们要将栈排空,这里我们可以直接添加一个高度为 $0$ 的矩形方便实现,写成代码也就是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
stack <int> s1,s2;

int work(int x) {
int ans = 0;
while (!s1.empty()) s1.pop();//清空两个栈
while (!s2.empty()) s2.pop();
s1.push(0);s2.push(0);//保证不访问空栈
for (int i = 1;i <= m + 1;++i) {
int now = h[x][i];//当前位置最大的 F 连续高度
if (now > s1.top()) {s1.push(now),s2.push(1);}//直接进栈的情况
else {
int wid = 0;
while (!s1.empty() && now < s1.top()) {
wid += s2.top();//累加高度
ans = max(ans,wid * s1.top();//更新答案
s1.pop(),s2.pop();
}
s1.push(now),s2.push(wid+1);//最后入栈
}
}
return ans;
}

对于每一行,我们都执行一个这样的过程

1
2
int ans = 0;
for (int i = 1;i <= n;++i) ans = max(ans,work(i));

时间复杂度 $O(nm)$

代码

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
#include <cstring>
#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <stack>
#include <algorithm>
using namespace std;
#define ll long long
#define ri register int

char buf[1 << 20], *p1, *p2;
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2)?EOF: *p1++)
inline int read() {
ri v = getchar();int f = 1,t = 0;
while (!isdigit(v)) {if (v == '-')f = -1;v = getchar();}
while (isdigit(v)) {t = t * 10 + v - 48;v = getchar();}
return t *= f;
}

const int N = 1e3+10;

int n,m,h[N][N];

char g[N][N];

stack <int> s1,s2;

int work(int x) {
int ans = 0;
while (!s1.empty()) s1.pop();
while (!s2.empty()) s2.pop();
s1.push(0);s2.push(0);
for (int i = 1;i <= m + 1;++i) {
int now = h[x][i];
if (now > s1.top()) {s1.push(now),s2.push(1);}
else {
int wid = 0;
while (!s1.empty() && now < s1.top()) {
wid += s2.top();
ans = max(ans,wid * s1.top());
s1.pop(),s2.pop();
}
s1.push(now),s2.push(wid+1);
}
}
return ans;
}

void solve() {
memset(h,0,sizeof h);
cin >> n >> m;
for (int i = 1;i <= n;++i) {
for (int j = 1;j <= m;++j) {
cin >> g[i][j];
if (g[i][j] == 'F') h[i][j] = h[i-1][j] + 1;
}
}
int ans = 0;
for (int i = 1;i <= n;++i) ans = max(ans,work(i));
printf("%d\n",ans * 3);
}

signed main() {
int T;cin >> T;
while (T--) solve();
return 0;
}