AtCoder Education DP Contest X Tower 题解

· · 题解

题目链接

题目大意：有 n 块积木，每块有 3 个属性，w_i,s_i,v_i，分别表示这块积木的重量、承受能力和价值。要从中选择一些积木以任意顺序堆成一堆，必须满足一堆中每个积木的承受能力都 \geq 上面所有积木的承受能力，求这一堆的总最大价值。

数据范围：n\leq 1000,w_i,s_i\leq10^4。

感觉这题难点在于怎么证明贪心策略？

一眼知道用 exchange arguments，考虑怎么贪心。

如果先把 i 放在下面再放 j 还能往上堆 s_j-w_i，反之还能堆 s_i-w_j。所以若要把 i 放在下面则必须满足 s_j-w_i<s_i-w_j，也就是 w_i+s_i>w_j+s_j。

下面按 w_i+s_i 从小到大排序完了打个 01 背包跑路。

/**
 *  author: Jerry_Jiang
**/

#include <bits/stdc++.h>

#define LOCAL

using namespace std;

const int N = 1e3 + 5, W = 2e4 + 5;

int n;
long long dp[N][W];
struct block {
    int w, s;
    long long v;
    bool operator < (const block &x) const {
        return w + s < x.w + x.s;
    }
} a[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        cin >> a[i].w >> a[i].s >> a[i].v;
    }
    sort(a + 1, a + n + 1);
    memset(dp, -0x3f, sizeof(dp));
    dp[0][0] = 0;
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j < W; j++) {
            dp[i][j] = dp[i - 1][j];
            if(j >= a[i].w && j - a[i].w <= a[i].s) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - a[i].w] + a[i].v);
            }
        }
    }
    cout << *max_element(dp[n], dp[n] + W) << '\n';
    return 0;
}