题目链接：Codeforces 1199F

有一个大小为 $n \times n$ 的网格图。其中一些格子是黑色的，其余格子都是白色的。你每次操作可以任意选择一个大小为 $h \times w$ 的矩形并把它全部染成白色，花费为 $\max(h, w)$。现在你想把所有格子都染成白色，请求出最小花费。

数据范围：$1 \le n \le 50$。

Solution

分析可知：如果一个矩形可以被分割当且仅当它存在一行或者一列全为白色。这样一来我们就可以 $\text{DP}$ 了，设 $f(x1, y1, x2, y2)$ 表示将矩形 $(x1, y1), (x2, y2)$ 染成白色的代价。如果可以分割，则枚举行列进行转移；否则该矩形的答案为 $\max(x2 - x1 + 1, y2 - y1 + 1)$。

时间复杂度：$\mathcal O(n ^ 5)$。

Code

#include <cstdio>
#include <cstring>
#include <algorithm>

const int N = 50 + 5;

int n, a[N][N], r[N][N], c[N][N], f[N][N][N][N];
char s[N][N];

int dfs(int x1, int y1, int x2, int y2) {
    if (x1 > x2 || y1 > y2) return 0;
    if (x1 == x2 && y1 == y2) return s[x1][y1] == '#' ? 1 : 0;
    if (f[x1][y1][x2][y2] >= 0) return f[x1][y1][x2][y2];
    int ans = std::max(x2 - x1 + 1, y2 - y1 + 1);
    for (int i = x1; i <= x2; i++) {
        if (r[i][y2] - r[i][y1 - 1] == 0) {
            ans = std::min(ans, dfs(x1, y1, i - 1, y2) + dfs(i + 1, y1, x2, y2));
        }
    }
    for (int i = y1; i <= y2; i++) {
        if (c[x2][i] - c[x1 - 1][i] == 0) {
            ans = std::min(ans, dfs(x1, y1, x2, i - 1) + dfs(x1, i + 1, x2, y2));
        }
    }
    return f[x1][y1][x2][y2] = ans;
}
int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s[i] + 1);
        for (int j = 1; j <= n; j++) a[i][j] = (s[i][j] == '#' ? 1 : 0);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            r[i][j] = r[i][j - 1] + a[i][j];
            c[i][j] = c[i - 1][j] + a[i][j];
        }
    }
    memset(f, -1, sizeof(f));
    printf("%d\n", dfs(1, 1, n, n));
    return 0;
}