[USACO05MAR] Space Elevator 太空电梯
先按允许高度排序，再用多重 01 背包判断哪些电梯高度可达。
OJ: luogu
题目 ID: P6771
难度:普及+/提高
标签:动态规划多重背包排序
日期: 2026-06-19 16:51
题意
有 n 种方块，每种方块有：
- 高度
h_i - 数量
c_i - 允许到达的最高高度
a_i
如果某个方块被放到高度 x 的位置，那么它整个方块的最高点不能超过 a_i。
因此，只有当当前堆叠高度足够低时，这种方块才能放上去。
目标是堆出尽可能高的太空电梯。
这张表把题意翻成了背包模型：
| 原题对象 | 含义 |
|---|---|
| 一种方块 | 有数量上限的物品 |
| 方块高度 | 物品重量 |
允许高度 a_i |
这类物品的使用上限 |
| 最高可达高度 | 目标答案 |
思路
一句话本质：按限高排序后，做多重背包可行性 DP——限高小的必须在下面，排序消除了依赖顺序的不确定性。
先看最直接的暴力：
import sys
data = list(map(int, sys.stdin.buffer.read().split()))
N = data[0]
blocks = []
idx = 1
for _ in range(N):
h, a, c = data[idx], data[idx + 1], data[idx + 2]
idx += 3
blocks.append((a, h, c))
blocks.sort()
best = 0
def dfs(i, cur_h):
global best
if i == N:
best = max(best, cur_h)
return
a, h, c = blocks[i]
dfs(i + 1, cur_h)
for k in range(1, c + 1):
nh = cur_h + k * h
if nh <= a:
dfs(i + 1, nh)
dfs(0, 0)
print(best)brute.py 枚举每种方块用
为什么必须先按
如果不排序，就可能把限高小的方块放在限高大的方块之上。但题目要求方块的任何部分不能超过自己的
所以先处理
排序后怎么建模？
每种方块有数量上限，是多重背包。"高度"是物品重量，目标是看哪些高度可达。设
数量限制怎么处理而不炸复杂度？
不用二进制拆分，用
转移条件是什么？
对于当前方块高度
代码
#include <bits/stdc++.h>
using namespace std;
struct Block {
int h, a, c;
bool operator<(const Block& o) const {
return a < o.a; // 按最大高度限制升序排列
}
};
const int MAXH = 40005;
int N;
Block b[405];
// dp[j] 表示高度 j 是否可达。
bool dp[MAXH];
// used[j] 记录在处理当前类型方块时，达到高度 j 已经用了几个该方块。
int used[MAXH];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N;
for (int i = 0; i < N; i++) {
cin >> b[i].h >> b[i].a >> b[i].c;
}
sort(b, b + N); // 先处理最大高度限制低的方块
dp[0] = true;
for (int i = 0; i < N; i++) {
int h = b[i].h, a = b[i].a, c = b[i].c;
fill(used, used + a + 1, 0); // 每种方块重新计数
// 多重背包可行性，用 used 数组限制每种的用量。
for (int j = h; j <= a; j++) {
if (!dp[j] && dp[j - h] && used[j - h] < c) {
dp[j] = true;
used[j] = used[j - h] + 1;
}
}
}
// 从最大高度向下找第一个可达高度。
for (int j = b[N - 1].a; j >= 0; j--) {
if (dp[j]) {
cout << j << '\n';
break;
}
}
return 0;
}复杂度
- 时间复杂度：
，其中 A是最大允许高度 - 空间复杂度：
总结
这题的关键是排序：
- 先按
a_i从小到大处理 - 再把“能不能放”转成“当前高度是否足够低”
一旦状态写成“高度是否可达”，问题就变成了一个很标准的多重背包可达性 DP。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
