Moe's CF Life

Appearance

F. Color Rows and Columns - 题解 ​

比赛与标签 ​

比赛: Codeforces Round 966 (Div. 3) 标签: dp, greedy, implementation, math 难度: *1900

题目大意喵~ ​

你好呀，未来的算法大师！这道题是这样的喵~

我们有 n 个不同大小的矩形，第 i 个矩形的宽是 a_i，高是 b_i。我们可以用魔法画笔给任意一个矩形里的格子涂色，这个操作可以无限次进行。

每当我们把一个矩形的一整行或者一整列全部涂满颜色时，我们就能得到 1 分！我们的任务是，要获得至少 k 分，同时希望涂色的格子总数（也就是操作次数）尽可能少。

如果无论如何都凑不够 k 分，就要告诉出题人这是不可能的（输出-1），否则就告诉他最少需要涂多少个格子，喵~

解题思路喵~ ​

这道题看起来有点复杂，但别担心，跟着本喵的思路一步步来，你就能轻松搞定它啦！

1. 先从单个矩形下手！ ​

我们先不想那么多矩形，只考虑一个宽为 a、高为 b 的矩形。如果我们决定要涂满 r 行和 c 列，能得多少分呢？很显然，是 r + c 分，对吧？

那代价（涂色格子数）是多少呢？r 行总共有 r * a 个格子，c 列总共有 c * b 个格子。但是，这 r 行和 c 列相交的地方（一个 r * c 的小矩形）被我们算了两次哦！根据容斥原理，我们要把多算的部分减掉。所以，总的涂色格子数是 r * a + c * b - r * c。

现在，对于这一个矩形，我们就可以通过遍历所有可能的 r (从0到b) 和 c (从0到a)，来找出获得 p 分的最小代价是多少了，喵！

2. 多个矩形？这是分组背包问题呀！ ​

当我们有 n 个矩形时，问题就变成了：对于每个矩形，我们可以选择一个“涂色方案”（即获得 p 分，花费 cost 代价），然后把这些来自不同矩形的方案组合起来，使得总得分至少为 k，且总代价最小。

这听起来是不是很像…… 分组背包问题？

  • 背包容量: 目标分数 k。
  • 物品组: 每个矩形就是一个物品组。
  • 组内物品: 对于一个矩形，选择涂 r 行 c 列就是一个“物品”，它的“重量”是得分 r+c，“价值”是负的代价 - (r*a + c*b - r*c)（因为我们要求代价最小化，相当于价值最大化）。

所以，我们可以用动态规划来解决！

3. DP状态设计与转移 ​

我们定义一个 dp 数组，dp[j] 表示：从已经考虑过的矩形中，获得 j 分所需要的最小总代价。

我们的目标就是求出 dp[k]！

DP的流程是这样的：

  1. 初始化 dp 数组。dp[0] = 0 (获得0分不需要任何代价)，其他 dp[j] 都设为一个超大的值（比如 INF），表示暂时无法达到。
  2. 我们依次遍历每个矩形。对于当前正在考虑的矩形 i（大小为 a x b），我们需要先计算出只用这一个矩形能产生的各种得分和对应的最小代价。
  3. 我们创建一个临时的代价数组 h，h[p] 表示只用当前这一个矩形，获得至少 p 分所需的最小代价。
    • 怎么算 h[p] 呢？我们先遍历所有可能的行数 r 和列数 c，算出得分 points = r + c 和代价 cost = r*a + c*b - r*c。然后更新 h[points] = min(h[points], cost)。
    • 算完所有 r, c 组合后，h[p] 存的是获得恰好 p 分的最小代价。但题目要求是至少 k 分，所以我们可以做一个小小的贪心优化：如果用更小的代价能获得更多的分数，那肯定更划算！所以我们从后往前更新一下 h 数组：h[p] = min(h[p], h[p+1])。这样 h[p] 就变成了获得至少 p 分的最小代价了，喵~
  4. 现在，我们有了旧的 dp 状态（考虑前 i-1 个矩形）和当前矩形 i 的代价信息 h，就可以更新 dp 状态了。我们创建一个 new_dp 数组来存放新状态：
    • new_dp[min(j + p, k)] = min(new_dp[min(j + p, k)], dp[j] + h[p])
    • 这个转移方程的意思是：如果之前用 dp[j] 的代价获得了 j 分，现在从当前矩形再获得 p 分（代价为 h[p]），那么我们总共就能用 dp[j] + h[p] 的代价获得 j + p 分。因为我们最多只需要 k 分，所以得分超过 k 的都算作 k 分。
  5. 遍历完所有 j 和 p 后，用 new_dp 更新 dp 数组。
  6. 处理完所有 n 个矩形后，dp[k] 就是我们想要的最终答案啦！如果 dp[k] 还是 INF，说明无法凑够 k 分。

这样，一步步地，我们就把复杂的问题分解成可以解决的小问题了，是不是很清晰了呢？加油，你一定可以的！

代码实现喵~ ​

cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

// 用一个很大的数表示无穷大，防止溢出喵~
const long long INF = 1e18;

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

    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vector<pair<int, int>> rects(n);
        for (int i = 0; i < n; i++) {
            cin >> rects[i].first >> rects[i].second;
        }

        // dp[j] 表示获得 j 分所需的最小代价
        vector<long long> dp(k + 1, INF);
        dp[0] = 0; // 获得0分不需要代价

        // 遍历每一个矩形（每一个物品组）
        for (auto [a, b] : rects) {
            // h[p] 表示只用当前这个矩形，获得至少 p 分的最小代价
            vector<long long> h(k + 1, INF);

            // 遍历所有可能的行数 r 和列数 c
            for (int r = 0; r <= b; r++) {
                for (int c = 0; c <= a; c++) {
                    int points = r + c;
                    // 代价计算公式：r行面积 + c列面积 - 重叠面积
                    long long cost_val = 1LL * r * a + 1LL * c * b - 1LL * r * c;

                    // 如果得分已经超过k，我们只关心k分的情况
                    if (points >= k) {
                        h[k] = min(h[k], cost_val);
                    } else {
                        h[points] = min(h[points], cost_val);
                    }
                }
            }

            // 关键优化：从后往前更新h，使得h[p]表示获得【至少】p分的最小代价
            // 如果获得 p+1 分的代价比 p 分还小，那肯定选 p+1 分的方案呀！
            for (int q = k - 1; q >= 0; q--) {
                h[q] = min(h[q], h[q + 1]);
            }

            // 创建新的dp表，用于合并当前矩形的结果
            vector<long long> new_dp(k + 1, INF);
            // 遍历旧的dp状态
            for (int j = 0; j <= k; j++) {
                // 如果旧状态 dp[j] 本身就无法达到，就跳过
                if (dp[j] == INF) continue;
                // 遍历当前矩形能提供的分数
                for (int q = 0; q <= k; q++) {
                    // 总得分 = 旧得分 + 新得分 (最多为k)
                    int new_j = min(j + q, k);
                    // 总代价 = 旧代价 + 新代价
                    long long total_cost = dp[j] + h[q];
                    // 更新新状态的最小代价
                    new_dp[new_j] = min(new_dp[new_j], total_cost);
                }
            }
            // 用新状态覆盖旧状态，准备处理下一个矩形
            dp = new_dp;
        }

        // 处理完所有矩形后，检查最终结果
        if (dp[k] == INF) {
            cout << -1 << '\n';
        } else {
            cout << dp[k] << '\n';
        }
    }
    return 0;
}

复杂度分析的说 ​

  • 时间复杂度: O(N * (max_a * max_b + K^2)) 的说。 对于 N 个矩形中的每一个，我们都需要：

    1. 计算当前矩形的代价数组 h，这需要遍历所有 r 和 c，复杂度是 O(max_a * max_b)。
    2. 更新 dp 数组，这需要两层循环，遍历 j (从0到k) 和 q (从0到k)，复杂度是 O(K^2)。 所以总的时间复杂度就是 N * (max_a * max_b + K^2)。根据题目限制 (n<=1000, k<=100, a,b<=100，且所有测试用例的 n 的总和不超过1000)，这个复杂度是完全可以接受的，喵~

  • 空间复杂度: O(K) 的说。 我们主要用了 dp, new_dp, h 这几个数组，它们的大小都和 k 相关，所以空间复杂度是 O(K)。

知识点与总结喵！ ​

这道题是一道非常经典的分组背包DP问题，融合了数学和贪心的思想，很考验综合能力呢！

  1. 核心算法: 动态规划 (分组背包模型)。把每个矩形看作一个物品组，从中选择一个最优的“得分-代价”方案来更新全局DP状态。
  2. 数学原理: 容斥原理。计算涂色代价时 cost = r*a + c*b - r*c 是解题的第一步，也是关键一步。
  3. 贪心优化: 将“恰好获得p分”的代价数组 h 通过后缀最小值操作 h[p] = min(h[p], h[p+1]) 转换为“至少获得p分”的代价，这是一个非常实用的小技巧，能简化问题！
  4. 编程技巧:
    • 注意代价 cost_val 可能会很大，100*100*100 已经超过了 int 的范围，所以记得使用 long long 来存储代价，防止溢出。
    • 用一个极大值 INF 来表示“无法到达”的状态是DP中的常用手法。

希望这篇题解能帮到你，让你对DP的理解更深一层！继续努力，你超棒的，喵~ >w<

Released under the MIT License.

Copyright © 2024-present Moe