[ZJOI 2007] 棋盘制作

题目大意

给定一个 n×mn \times m 的黑白网格,在其上找一个面积最大的正方形、矩形的黑白相间的网格,输出最大面积。

1n,  m2,0001 \leqslant n, \; m \leqslant 2,000

题目链接

【ZJOI 2007】棋盘制作 - Luogu 1169

题解

悬线法。

对每个格子 (i,j)(i, j) ,求出 up(i,j)up(i, j)left(i,j)left(i, j)right(i,j)right(i, j) 分别表示从该格子向上最远能取多远、以及在取这么远的情况下能向左/右拓展到的最远位置。

up(i,j)={1i=1  or  (i,j)=(i1,j)up(i1,j)+1(i,j)(i1,j)left(i,j)={loi=1  or  (i,j)=(i1,j)max(left(i1,j),  lo)(i,j)(i1,j)right(i,j)={roi=1  or  (i,j)=(i1,j)max(right(i1,j),  ro)(i,j)(i1,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} \\

其中,lolo 每行从左开始计算,表示当前格向左最远能到的位置,roro 与之相反。

扫一遍网格即可求出以上三个数组。此时,对于每个格子 (i,j)(i, j)up(i,j)×(right(i,j)left(i,j)+1)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 <cstdio>
#include <algorithm>
const int MAXN = 2005;
int main() {
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("%d\n%d\n", ansSqr, ansRect);
return 0;
}