T2-11 Space Elevator

题意理解

有 $N$ 种方块，第 $i$ 种高度 $h_i$，数量 $c_i$，且使用时顶部高度不能超过 $a_i$。求能堆出的最大高度。

---

思路分析

这是带限制的多重背包问题。

关键点： 必须按高度限制 $a_i$ 从小到大排序后处理。因为限制小的方块必须放在下面，否则后面无法再放它。

设 $dp[j]$ 表示高度 $j$ 是否可达。

状态转移（多重背包）：

对于每种方块（排序后），枚举使用的数量 $k$（$1 \leq k \leq c_i$）：

$$dp[j] = dp[j] \text{ or } dp[j - h_i]$$

转移时需满足 $j \leq a_i$（高度限制）

边界条件：

• $dp[0] = true$：高度 0 可达

答案： $dp[j] = true$ 的最大 $j$

---

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXH = 40005;  // 最大高度

int n;           // 方块种类数
bool dp[MAXH];   // dp[j]表示高度j是否可达

struct Block {   // 方块结构体
    int h, a, c; // 高度、限制、数量
} b[405];

bool cmp(Block x, Block y) {  // 按高度限制排序
    return x.a < y.a;
}

int main() {
    cin >> n;  // 读入方块种类数
    
    for (int i = 1; i <= n; i++) {  // 读入每种方块信息
        cin >> b[i].h >> b[i].a >> b[i].c;
    }
    
    sort(b + 1, b + n + 1, cmp);  // 按高度限制从小到大排序
    
    dp[0] = true;  // 边界：高度0可达
    int ans = 0;   // 答案
    
    for (int i = 1; i <= n; i++) {  // 枚举每种方块
        for (int k = 1; k <= b[i].c; k++) {  // 多重背包，枚举使用数量
            for (int j = b[i].a; j >= b[i].h; j--) {  // 逆序枚举高度，不超过限制
                if (dp[j - b[i].h]) {  // 如果j-h可达
                    dp[j] = true;      // 则j也可达
                }
            }
        }
    }
    
    for (int j = MAXH - 1; j >= 0; j--) {  // 找最大可达高度
        if (dp[j]) {
            ans = j;
            break;
        }
    }
    
    cout << ans << endl;  // 输出答案
    return 0;
}