[蓝桥杯 2022 国 B] 搬砖 题解

· · 题解

原题传送门

Part 0

首先浏览题面，当看到数据范围 n \leq 1000, w_i \leq 20, v_i \leq 20000 时，就容易想到 \text{01} 背包做法。但是，为了让砖块的价值总和最大，我们不能直接对其进行 \text{01} 背包，必须先将砖块排序。否则，如果让一块很大的砖先做，较小的砖就无法在此基础上进行转移（原本价值可以直接累加），从而完美避开最优解。

按照什么样的顺序进行排序呢（这一部分本人看了 @王熙文 大佬的题解才明白，但对其中的一些小错误进行更正）？

首先，我们有两块砖 i, j，使得 w_i + v_i \leq w_j + v_j，我们假设 i 一定排在 j 前，即 j 可以排在前的情况，i 必定能排在前。

设 W 表示排在 i, j 前砖块的质量和。若 j 能排在前，则必须满足：

v_j \geq W, v_i \geq W + w_j

此时，若将 i 排在前，则必须满足：

v_i \geq W, v_j \geq W + w_i

由于 w_j \geq 0，所以 v_i \geq W 满足。接着，我们将 v_i \geq W + w_j 移项，得：

v_i - w_j \geq W

然后，将表示 i, j 关系的不等式 w_i + v_i \leq w_j + v_j 也移项，得：

v_j - w_i \geq v_i - w_j

二者结合，得 v_j - w_i \geq W，即 v_j \geq W + w_i。由此，便证明了最初的假设。

Part 1

代码写起来就很容易了。需要注意的是，为方便转移，\text{01} 背包中 dp_i 表示前几块砖重量和为 i 的最大价值。

AC Code

#include <bits/stdc++.h>
using namespace std;
int n, m, ans, dp[20030];
struct node { int w, v; } a[1010]; //砖块
bool cmp(node pre, node nxt) { return pre.w + pre.v <= nxt.w + nxt.v; } //排序 
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++ i) cin >> a[i].w >> a[i].v;
    sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; ++ i)
        for (int j = a[i].w + a[i].v; j >= a[i].w; -- j)
            dp[j] = max(dp[j], dp[j - a[i].w] + a[i].v), //01背包 
            ans = max(ans, dp[j]); //求最大 
    cout << ans;
    return 0;
}

自认为马蜂比较清晰简短，希望大家看得懂，并祝大家 Codeing 愉快。