Moe's CF Life

Appearance

F. Rectangle Painting 1 - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 576 (Div. 2) 标签: dp, *2300 难度: *2300

喵~ 任务是什么呀？ ​

主人，你好呀~！(ฅ'ω'ฅ) 这次我们的任务是在一个 n x n 的棋盘上施展魔法哦！棋盘上有些格子是黑色的（用 '#' 表示），有些是白色的（用 '.' 表示）。

我们的魔法是：选择一个任意大小的矩形区域，然后把它里面所有的格子都变成白色！不过，这个魔法是需要消耗魔力的呐。如果矩形的大小是 h x w（高h，宽w），那么消耗的魔力就是 max(h, w)。

我们的最终目标，就是用最少的总魔力，把整个棋盘都变成纯白色！听起来是不是很有趣的说？

猫猫的思考时间！ ​

看到 n 最大只有 50，猫猫的直觉告诉我，这很可能是一个需要动用智慧的动态规划（DP）问题喵~！

问题的核心是“把一个区域变白”，这启发我们可以把大问题分解成小问题来解决。比如说，要清理整个 n x n 的大棋盘，我们可以考虑如何清理其中的一小块矩形区域。这就引出了我们 DP 的核心思路！

1. 定义状态 ​

我们就用 dp[r1][c1][r2][c2] 来表示一个状态吧！它代表的意义是：将左上角坐标为 (r1, c1)，右下角坐标为 (r2, c2) 的这个矩形区域全部涂成白色的最小花费。我们的最终答案，自然就是 dp[1][1][n][n] 啦！

2. 思考转移方程 ​

对于任何一个矩形区域 (r1, c1) -> (r2, c2)，我们有什么办法把它变白呢？猫猫想到了两种策略：

策略一：一招制敌喵！ 最简单粗暴的方法，就是直接用一次魔法，把整个矩形 (r1, c1) -> (r2, c2) 全部涂白！ 这个矩形的高度 h = r2 - r1 + 1，宽度 w = c2 - c1 + 1。根据规则，这次操作的花费是 max(h, w)。 这是一个保底的方案，我们的花费肯定不会比这个更高。

策略二：分而治之喵！ 我们不一次性涂完，而是把这个大矩形切成两个小矩形，然后分别计算涂白它们的最小花费，最后把花费加起来。 怎么切呢？也有两种切法：

  • 水平切割：我们可以在第 i 行和第 i+1 行之间切一刀（其中 r1 <= i < r2）。这样，原来的大矩形就被分成了上下两个小矩形：(r1, c1) -> (i, c2) 和 (i+1, c1) -> (r2, c2)。总花费就是 dp[r1][c1][i][c2] + dp[i+1][c1][r2][c2]。我们可以尝试所有可能的水平切割位置 i，然后取一个最小值。

  • 垂直切割：同理，我们也可以在第 j 列和第 j+1 列之间切一刀（其中 c1 <= j < c2）。这样就分成了左右两个小矩形：(r1, c1) -> (r2, j) 和 (r1, j+1) -> (r2, c2)。总花费就是 dp[r1][c1][r2][j] + dp[r1][j+1][r2][c2]。我们也要尝试所有可能的垂直切割位置 j，取一个最小值。

总结一下，dp[r1][c1][r2][c2] 的值，就是以上所有可能性中的最小值！也就是： dp[r1][c1][r2][c2] = min( 策略一的花费, min(所有水平切割的花费), min(所有垂直切割的花费) )

3. 确定边界条件（Base Case） ​

当我们的矩形小到不能再小，也就是一个 1x1 的格子 (r, c) -> (r, c) 时，情况就非常简单了：

  • 如果这个格子 grid[r][c] 本来就是白色的 .，那我们什么都不用做，花费是 0。
  • 如果这个格子是黑色的 #，我们就必须用一次 1x1 的魔法涂白它，花费是 max(1, 1) = 1。

4. 记忆化搜索 ​

直接用递归来实现上面的思路，会发现很多子问题被重复计算了，这可不行喵！所以我们要用一个 memo 数组把计算过的结果存起来。每次进入函数，先查表，如果已经算过了，就直接返回结果。这也就是记忆化搜索啦！

这样，一个清晰的解题思路就诞生了！(๑•̀ㅂ•́)و✧

让代码动起来喵！ ​

下面就是把我们的想法变成现实的代码啦，猫猫已经加上了详细的注释，希望能帮到你哟~

cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <cstring>

// 全局变量，方便在函数里使用喵~
int n;
// 用1-based索引，这样处理边界更方便一点
char grid[51][51];
// 记忆化数组，dp[r1][c1][r2][c2]的值就存在这里
// 初始化为-1，表示这个状态还没计算过
int memo[51][51][51][51];

// 这个函数计算把 (r1, c1) 到 (r2, c2) 的矩形涂白的最小代价
int solve(int r1, int c1, int r2, int c2) {
    // 如果这个子问题已经算过了，直接返回存好的结果，不重复计算！
    if (memo[r1][c1][r2][c2] != -1) {
        return memo[r1][c1][r2][c2];
    }

    // 递归的终止条件：1x1 的小格子
    // 如果格子是黑'#'，就需要花费1来涂白它 (max(1,1)=1)
    // 如果是白'.'，就不需要花费，代价是0
    if (r1 == r2 && c1 == c2) {
        return memo[r1][c1][r2][c2] = (grid[r1][c1] == '#');
    }

    // 策略1：直接一笔把整个矩形涂掉！
    int h = r2 - r1 + 1;
    int w = c2 - c1 + 1;
    // 这是我们的一个备选答案，也是初始的最小代价
    int min_cost = std::max(h, w);

    // 策略2：把问题分解！
    // 尝试所有可能的水平切割
    for (int i = r1; i < r2; ++i) {
        // 分成上下两块，代价是两块代价之和
        min_cost = std::min(min_cost, solve(r1, c1, i, c2) + solve(i + 1, c1, r2, c2));
    }

    // 尝试所有可能的垂直切割
    for (int j = c1; j < c2; ++j) {
        // 分成左右两块，代价也是两块代价之和
        min_cost = std::min(min_cost, solve(r1, c1, r2, j) + solve(r1, j + 1, r2, c2));
    }

    // 找到了最小代价，存到记忆化数组里，然后返回~
    return memo[r1][c1][r2][c2] = min_cost;
}

int main() {
    // 加速输入输出，让程序跑得更快一点喵
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    // 读取棋盘大小
    std::cin >> n;

    // 读取棋盘布局，注意我们是从(1,1)开始存的
    std::string row_str;
    for (int i = 1; i <= n; ++i) {
        std::cin >> row_str;
        for (int j = 1; j <= n; ++j) {
            grid[i][j] = row_str[j - 1];
        }
    }

    // 把记忆化数组全部初始化为 -1
    // memset 是个好用的函数，可以快速填充内存区域
    memset(memo, -1, sizeof(memo));

    // 调用我们的解决函数，计算清理整个 n x n 棋盘的最小代价
    // 也就是从 (1,1) 到 (n,n) 的子问题
    std::cout << solve(1, 1, n, n) << std::endl;

    return 0;
}

跑得快不快呀？ ​

  • 时间复杂度: O(n⁵) 的说 我们有四个变量 r1, c1, r2, c2 来定义状态，每个变量的范围都是 1 到 n，所以总共有 O(n⁴) 个不同的状态（子问题）。对于每个状态，我们需要 O(n) 的时间来进行水平和垂直的切割尝试。所以总的时间复杂度就是 状态数 × 每个状态的计算时间 = O(n⁴) * O(n) = O(n⁵)。对于 n=50 来说，50⁵ 大约是 3.125 * 10⁸，虽然看起来很大，但由于常数因子很小，并且有记忆化剪枝，实际上跑得飞快，是可以通过的！

  • 空间复杂度: O(n⁴) 的说 我们主要的开销是那个四维的 memo 数组，它的大小是 n x n x n x n，所以空间复杂度是 O(n⁴)。当 n=50 时，50⁴ = 6,250,000，每个 int 占 4 字节，总共大约需要 25MB 内存，完全在题目限制的 256MB 以内，没问题的啦！

喵喵的小课堂~ ​

这道题是一道非常经典的 区间/矩阵动态规划 题目，它的解法和 "矩阵链乘法" 问题很相似哦！

  • 核心算法: 动态规划 + 记忆化搜索。当问题可以被分解为结构相同的子问题，并且子问题之间有重叠时，DP 就是我们的好朋友！
  • 状态设计: 能否正确地定义出 dp[r1][c1][r2][c2] 是解题的关键。抓住 "解决一个矩形区域" 这个核心，状态就自然而然地出来了。
  • 转移逻辑: 思考解决当前问题的几种基本操作。在这里，就是 "一次性解决" 和 "分解成小问题解决"。把所有可能性都考虑到，然后取最优，就是 DP 转移方程的精髓。
  • 编程技巧: 使用记忆化搜索（自顶向下的 DP）通常比直接写循环（自底向上的 DP）要更直观，代码也更简洁。同时，memset 初始化数组是个很方便的技巧。

希望这篇题解能帮助你理解这道题的奥秘！继续加油，探索更多算法的乐趣吧，喵~ (≧▽≦)

Released under the MIT License.

Copyright © 2024-present Moe