重要算法思想：贪心、二分、正难则反、多重与完全背包精练

题目清单

1. Space Elevator 太空电梯

题目： P6771 [USACO05MAR] Space Elevator 太空电梯

解法：贪心 + 动态规划（多重背包）

贪心： 当我们从前往后考虑每一个方块的时候，限定高度 a[i] 小的应该优先考虑。因为如果先放限定高度大的，这些限定高度小的就没法放了。因此，先对所有的方块按照限定高度 a[i] 从小到大排序。

接下来的问题就是挑一些方块出来，在不超过每一种方块的限定高度下，看看能堆成的最大高度是多少。正好是多重背包问题。

1. 状态表示： f[i][j] 表示：从前 i 个方块中挑选，总高度不超过 j 的情况下，最大的高度是多少。

结果： 整个 f 表中的最大值，就是我们要的结果。这里要注意，并不是 f[n][m]，因为有可能考虑不到第 n 个方块根本考虑不进去，最后一行根本就不会更新。

2. 状态转移方程： 根据第 i 个方块选的数量，可以分成 c[i] + 1 种情况，要的是所有情况的最大值。设选了 k 个方块，那么最大高度为 f[i - 1][j - k * h[i]] + k * h[i]。 注意限定条件，循环高度的时候不能超过 a[i]，并且 j - k * h >= 0。

3. 初始化： 取 max，全部初始化为 0。

4. 填表顺序： 从左到右，空间优化（第二层循环：逆序）从大到小

代码：

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 410, M = 4e4 + 10;
int n;
struct node {
    int h, a, c;
} e[N];
// int f[N][M]; 优化一维
int f[M];
bool cmp(node& x, node& y) {
    return x.a < y.a;
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> e[i].h >> e[i].a >> e[i].c;
    (e + , e +  + n, cmp);
     ret = ;
    
     ( i = ; i <= n; i++) {
         h = e[i].h, a = e[i].a, c = e[i].c;
         ( j = a; j >= ; j--) 
             ( k = ; k <= c && k * h <= j; k++) {
                f[j] = (f[j], f[j - k * h] + k * h);
            }
        ret = (ret, f[j]);
    }
    cout << ret << endl;
     ;
}