题目大意
给定一个 (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; }
|
近期评论