[USACO05MAR] Space Elevator 太空电梯

题意

有 n 种方块，每种方块有：

高度 h_i
数量 c_i
允许到达的最高高度 a_i

如果某个方块被放到高度 x 的位置，那么它整个方块的最高点不能超过 a_i。因此，只有当当前堆叠高度足够低时，这种方块才能放上去。

目标是堆出尽可能高的太空电梯。

这张表把题意翻成了背包模型：

原题对象	含义
一种方块	有数量上限的物品
方块高度	物品重量
允许高度 `a_i`	这类物品的使用上限
最高可达高度	目标答案

思路

先看最直接的暴力：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71#include <bits/stdc++.h>
using namespace std;

struct Block {
    int h;
    int c;
    int a;
};

int n;
vector<Block> blocks;
vector<int> choose_count; // choose_count[i] 表示第 i 种方块用了多少个
int answer = 0;

bool cmp_block(const Block &x, const Block &y) {
    return x.a < y.a;
}

bool check() {
    int cur_height = 0;
    for (int i = 0; i < n; i++) {
        cur_height += choose_count[i] * blocks[i].h;
        if (cur_height > blocks[i].a) {
            return false;
        }
    }
    return true;
}

int calc_height() {
    int height = 0;
    for (int i = 0; i < n; i++) {
        height += choose_count[i] * blocks[i].h;
    }
    return height;
}

// 暴力枚举每种方块用了多少次，叶子节点统一检查高度限制。
void dfs_choose(int dep) {
    if (dep == n) {
        if (check()) {
            int value = calc_height();
            if (answer < value) answer = value;
        }
        return;
    }

    for (int cnt = 0; cnt <= blocks[dep].c; cnt++) {
        choose_count[dep] = cnt;
        dfs_choose(dep + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    blocks.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> blocks[i].h >> blocks[i].a >> blocks[i].c;
    }

    sort(blocks.begin(), blocks.end(), cmp_block);

    choose_count.assign(n, 0);
    dfs_choose(0);
    cout << answer << '\n';

    return 0;
}

brute.cpp 把每种方块用了多少个看成一层选择：choose_count[i] 表示第 i 种方块使用数量。递归先生成完整计数序列，叶子节点再检查每一层高度是否超出限制。

这个做法正确，但复杂度很高，只适合小数据验证。

关键观察是：

如果把方块按 a_i 从小到大排序，那么前面处理的方块一定不会比后面更“宽松”。
对于某种方块，只能把它放在当前高度不超过 a_i - h_i 的位置上。
因为每种方块有数量上限，所以是多重背包。

于是设：

dp[h] 表示当前能否堆出高度 h

这张表说明状态定义：

状态	含义
`dp[h]`	高度 `h` 是否可达

对于每种方块：

如果它能放上去，就把当前可达高度再加上 h_i
数量有限，所以同一种方块要重复做 c_i 次 0/1 转移

DP 公式

设 $dp_h$ 表示当前能否堆出高度 $h$ 。初始化：

dp_0=true

把每种方块按高度上限从小到大处理。对第 $i$ 种方块，每使用一块高度 $h_i$ 的方块，就做一次 0/1 可达转移：

dp_{x+h_i}\leftarrow dp_{x+h_i}\lor dp_x\quad (x+h_i\leqslant a_i)

最终答案为可达的最大高度：

\max\{h\mid dp_h=true\}

公式解释：每类方块有高度上限和数量上限。按最大允许高度排序后，只在不超过当前上限的位置转移；重复做有限次 0/1 转移就表示数量限制。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54#include <bits/stdc++.h>
using namespace std;

struct Block {
    int h; // 方块高度
    int c; // 数量
    int a; // 允许到达的最高高度
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    vector<Block> blocks(n);
    int max_a = 0;
    for (int i = 0; i < n; i++) {
        cin >> blocks[i].h >> blocks[i].a >> blocks[i].c;
        max_a = max(max_a, blocks[i].a);
    }

    sort(blocks.begin(), blocks.end(), [](const Block &x, const Block &y) {
        return x.a < y.a;
    });

    // dp[h] = 当前能否堆出高度 h。
    vector<char> dp(max_a + 1, 0);
    dp[0] = 1;

    for (const auto &blk : blocks) {
        if (blk.h > blk.a) {
            continue;
        }

        // 每种方块最多使用 c 次，所以重复做 c 次 0/1 转移。
        for (int t = 0; t < blk.c; t++) {
            for (int h = blk.a - blk.h; h >= 0; h--) {
                if (!dp[h]) continue;
                dp[h + blk.h] = 1;
            }
        }
    }

    for (int h = max_a; h >= 0; h--) {
        if (dp[h]) {
            cout << h << '\n';
            break;
        }
    }

    return 0;
}

复杂度

时间复杂度： $O(∑ c_i * A)$ ，其中 A 是最大允许高度
空间复杂度： $O(A)$

总结

这题的关键是排序：

先按 a_i 从小到大处理
再把“能不能放”转成“当前高度是否足够低”

一旦状态写成“高度是否可达”，问题就变成了一个很标准的多重背包可达性 DP。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。