题目详细题解

问题理解

我们有 $n$ 个矩形，第 $i$ 个矩形的尺寸为 $a_i \times b_i$（宽 $\times$ 高）。每次操作可以涂色一个单元格。当某一行或某一列的所有单元格都被涂色时，获得 $1$ 分。目标是用最少的操作次数获得至少 $k$ 分。

关键观察：

• 在一个 $a_i \times b_i$ 的矩形中，涂满一行需要 $a_i$ 次操作，涂满一列需要 $b_i$ 次操作。
• 涂色策略的最优性：每次应该选择当前矩形中较短的那条边，涂满一整行或一整列。因为这样可以用较少的操作获得分数（行或列被完整涂色）。
• 例如：一个 $6 \times 3$ 的矩形，涂一列需要 $6$ 次操作获得 $1$ 分，涂一行需要 $3$ 次操作获得 $1$ 分，显然先涂行更优。

---

动态规划状态定义

设 $dp[i][j]$ 表示：只考虑前 $i$ 个矩形，恰好获得 $j$ 分所需的最少操作次数。

初始状态：
$dp[0][0] = 0$，表示没有矩形时获得 $0$ 分需要 $0$ 次操作。
$dp[0][j] = \infty$（用一个大数 $10^9$ 表示不可能）对于 $j > 0$。

最终答案：$\min(dp[n][k], dp[n][k+1], \dots, dp[n][\text{最大可能分数}])$，实际上我们只需要 $dp[n][k]$，因为获得更多分数通常需要更多操作，但题目要求至少 $k$ 分，所以也可能超过 $k$ 分。不过标程中直接使用 $dp[n][k]$，因为转移时保证了 $j$ 不超过 $k$，且 $k \le 100$ 较小，所以我们可以只维护到 $k$，超过 $k$ 的分数不需要记录。

---

状态转移

对于第 $i$ 个矩形（尺寸 $x = a_i$，$y = b_i$），我们需要考虑从这个矩形中可以获得多少分以及对应的最少操作次数。

如何计算从一个矩形中获得 $j$ 分的最少操作数？

这是一个子问题：给定一个 $x \times y$ 矩形，每次涂满当前较短的一边（整行或整列），获得 $1$ 分，问获得 $j$ 分最少需要涂多少格子？

贪心策略：

• 设当前矩形尺寸为 $x \times y$，且 $x \le y$（否则交换）。
• 涂一行（较短边）需要 $x$ 次操作，获得 $1$ 分，矩形变为 $(x-1) \times y$。
• 如果 $x$ 和 $y$ 相等，涂一行和一列操作数相同，但注意：涂完一行后矩形可能变成 $(x-1) \times y$，下一次比较时可能 $x-1 < y$，仍然涂行。

模拟过程：

• 初始矩形 $x, y$，总边长和 $s = x + y$。
• 我们按顺序涂色，每次选择较短边，记录操作数累加。
• 第 $1$ 分：涂较短边，操作数为 $\min(x, y)$，然后该边减 $1$。
• 第 $2$ 分：再次涂新的较短边，操作数为当前 $\min(x, y)$，依此类推。
• 直到涂完所有行和列（共 $x + y$ 分？不，最多只能获得 $x + y$ 分吗？）

注意：一个 $x \times y$ 矩形共有 $x$ 行和 $y$ 列，最多可以得 $x + y$ 分（当所有行和列都被涂满时）。但是，涂满最后一行时，所有列可能已经被涂过，但分数仍然增加。实际上，涂色的顺序决定了操作数。

关键结论（来自标程）： 设当前矩形尺寸为 $x, y$，总行数+列数 = $x + y$。
从该矩形中获得 $j$ 分（$0 \le j \le x+y$）的最少操作数可以通过以下方式计算：

• 初始化 $cost = 0$，当前 $x, y$ 为原始值。
• 对于 $t = 1$ 到 $j$：
  • 如果 $x \ge y$，则操作数增加 $y$，然后 $x$ 减 $1$（涂一列）
  • 否则，操作数增加 $x$，然后 $y$ 减 $1$（涂一行）
• 最终 $cost$ 就是获得 $j$ 分的最少操作数。

为什么这样是最优的？
每次涂较短边可以最小化当前步的操作数，且不影响后续选择（因为后续仍然面对一个矩形，只是某一边减少了 $1$）。这是一个标准的贪心证明：局部最优导致全局最优。

---

转移方程

对于第 $i$ 个矩形，我们预处理出数组 $c_j$ 表示：从这个矩形中获得恰好 $j$ 分所需的最少操作数，其中 $0 \le j \le a_i + b_i$，并且 $c_0 = 0$。

然后进行背包式转移：

$$dp[i+1][j_1 + j] = \min(dp[i+1][j_1 + j],\; dp[i][j_1] + c_j) $$

其中 $0 \le j_1 \le k$，$0 \le j \le \min(a_i+b_i, k - j_1)$，因为我们只需要分数到 $k$。

---

时间复杂度

• 每个矩形最多产生 $a_i + b_i \le 200$ 种分数选择。
• $n \le 1000$，$k \le 100$。
• 总复杂度 $O(n \cdot k \cdot \max(a_i+b_i)) \approx O(1000 \times 100 \times 200) = 2 \times 10^7$，可接受。

---

代码实现细节

标程中的循环：

for (int j = 0; j <= xy; ++j) {
    for (int j1 = 0; j1 + j <= k; ++j1) {
        dp[i+1][j1+j] = min(dp[i+1][j1+j], dp[i][j1] + cost);
    }
    if (j < xy) {
        if (x >= y) {
            x--, cost += y;
        } else {
            y--, cost += x;
        }
    }
}

• $xy = a_i + b_i$，$j$ 表示从当前矩形获得的分数。
• 每次循环开始时 $cost$ 是获得 $j$ 分的最小操作数（因为上一轮更新了 $cost$ 来获得 $j-1$ 分，这一轮再加一步得到 $j$ 分）。
• 注意 $x, y$ 在循环中被修改，所以需要初始复制 $x = a_i, y = b_i$。
• 当 $j = xy$ 时，所有行和列都被涂满，此时 $cost$ 是总操作数。

---

边界情况

• 如果 $dp[n][k] = 10^9$，说明无法获得 $k$ 分，输出 $-1$。
• 可能一个矩形获得超过 $k$ 分的情况，但由于我们只维护到 $k$ 分，所以不需要处理。

---

示例验证（第一个样例）

矩形 $6 \times 3$，$k=4$。

计算 $c_j$（$j$ 分所需操作数）：

• $j=0$：$c=0$
• 初始 $(6,3)$，涂行（较短 $3$），$cost=3$，$(5,3)$
• $j=1$：$c=3$
• 当前 $(5,3)$，涂行（$3$），$cost=6$，$(4,3)$
• $j=2$：$c=6$
• $(4,3)$，涂行（$3$），$cost=9$，$(3,3)$
• $j=3$：$c=9$
• $(3,3)$，相等，涂行（$3$），$cost=12$，$(2,3)$
• $j=4$：$c=12$
• 再继续 $(2,3)$ 涂列（$2$）得到 $j=5$，$c=14$ 等。

所以 $c_4 = 12$，$dp[1][4] = 0 + 12 = 12$，输出 $12$，匹配样例。

---

总结

本题是贪心 + 分组背包 DP 的结合：

• 每个矩形内部的最优涂色顺序是贪心的（每次涂较短边）。
• 不同矩形之间的分数分配是背包问题。
• 时间复杂度 $O(n \cdot k \cdot \max(a_i+b_i))$，空间可优化到 $O(k)$。