题目大意
给定一个 (n times m) 的黑白网格，在其上找一个面积最大的正方形、矩形的黑白相间的网格，输出最大面积。
(1 leqslant n, ; m leqslant 2,000)
题目链接
BZOJ 1057
题解
悬线法。
对每个格子 ((i, j)) ，求出 (up(i, j)) 、(left(i, j)) 、(right(i, j)) 分别表示从该格子向上最远能取多远、以及在取这么远的情况下能向左／右拓展到的最远位置。 [
up(i, j) =
begin{cases}
1 qquad i = 1 ; or ; (i, j) = (i - 1, j) \
up(i - 1, j) + 1 qquad (i, j) neq (i - 1, j) \
end{cases} \
left(i , j) =
begin{cases}
lo qquad i= 1 ; or ;(i, j) = (i - 1, j) \
max(left(i - 1, j), ; lo) qquad (i, j) neq (i - 1, j) \
end{cases} \
right(i , j) =
begin{cases}
ro qquad i = 1 ; or ; (i, j) = (i - 1, j) \
max(right(i - 1, j), ; ro) qquad (i, j) neq (i - 1, j) \
end{cases} \
] 其中，(lo) 每行从左开始计算，表示当前格向左最远能到的位置，(ro) 与之相反。
扫一遍网格即可求出以上三个数组。此时，对于每个格子 ((i, j)) ，(up(i, j) times (right(i, j) - left(i, j) + 1)) 表示该点能扩展出的最大的黑白相间的矩形。
代码
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
|
#include <algorithm>
const int MAXN = 2005;
int () {
int n, m;
scanf("%d %d", &n, &m);
static int mat[MAXN][MAXN], up[MAXN][MAXN], left[MAXN][MAXN], right[MAXN][MAXN];
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
scanf("%d", &mat[i][j]);
if (i == 1 || mat[i][j] == mat[i - 1][j]) up[i][j] = 1;
else up[i][j] = up[i - 1][j] + 1;
}
for (int i = 1; i <= n; i++) {
int lo = 1;
for (int j = 1; j <= m; j++) {
if (j == 1) {
left[i][j] = 1;
continue;
}
if (mat[i][j] == mat[i][j - 1]) lo = j;
left[i][j] = lo;
if (up[i][j] > 1) left[i][j] = std::max(left[i - 1][j], lo);
}
}
for (int i = 1; i <= n; i++) {
int ro = m;
for (int j = m; j; j--) {
if (j == m) {
right[i][j] = m;
continue;
}
if (mat[i][j] == mat[i][j + 1]) ro = j;
right[i][j] = ro;
if (up[i][j] > 1) right[i][j] = std::min(right[i - 1][j], ro);
}
}
int ansSqr = 0, ansRect = 0;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
int bottom = right[i][j] - left[i][j] + 1;
int height = up[i][j];
ansRect = std::max(ansRect, bottom * height);
ansSqr = std::max(ansSqr, std::min(bottom, height) * std::min(bottom, height));
}
printf("%dn%dn", ansSqr, ansRect);
return 0;
}
|
近期评论