Space Elevator 太空电梯（洛谷）

题目描述 奶牛们要去太空了！它们打算用方块建造一座太空电梯。

现在它们有 N 种方块，第 i 种方块有一个特定的高度 h_i，一定的数量 c_i 。

为了防止宇宙射线的破坏方块，第 i 种方块的任何部分不能超过高度 a_i 。

请用这些方块堆出最高的太空电梯。

输入格式 第一行，一个整数 N； 第二行到 N+1 行，每行三个整数 h_i, a_i, c_i ，数字之间用空格分隔。

输出格式 共一行，一个整数，为太空电梯的高度。

输入样例 3 7 40 3 5 23 8 2 52 6

输出样例 48

数据范围 对于 100% 的数据：1 ≤ N ≤ 400，1 ≤ h_i ≤ 100，1 ≤ c_i ≤ 10， 1 ≤ a_i ≤ 4×10⁴

---

题解 多重背包（优化1.0）：

第 i 种方块只能在 a_i 及以下的高度下使用，所以为了充分利用所有方块，需要以 a_i 为关键字，从小到大排序。

#include <iostream> #include <algorithm> using namespace std; struct node { int h, a, c; }s[410]; int n, f[40010]; bool cmp(node x, node y) { return x.a < y.a; } int main() { cin >> n; for (int i = 1; i <= n; i ++) cin >> s[i].h >> s[i].a >> s[i].c; sort(s + 1, s + n + 1, cmp); f[0] = 1; for (int i = 1; i <= n; i ++) for (int j = s[i].a; j >= s[i].h; j --) for (int k = 0; k * s[i].h <= j && k <= s[i].c; k ++) f[j] += f[j - k * s[i].h]; for (int i = s[n].a; i >= 0; i --) if(f[i]) { cout << i << endl; return 0; } }