第一题：星港补给舱调度
题意简化
有 N 个补给舱，第 i 个补给舱需要消耗 R[i] 燃料才能发射。
有 Q 次询问，每次给一个燃料数 X，问最多能发射多少个补给舱。
思路
想让发射数量尽可能多，就应该优先选择消耗燃料少的补给舱。
所以第一步：把所有 R[i] 从小到大排序。
排序后，如果想发射前 k 个补给舱，需要的总燃料就是：
为了快速算这个总和，使用前缀和：
对于每个询问 X，问题变成：
这个位置就是最多能发射的数量。
因为 R[i] 排序后都是非负消耗，所以前缀和 s[i] 一定是递增的，可以用二分。
参考代码
为什么要减 1
upper_bound(s, s + n + 1, x) 找到的是第一个 > x 的位置。
我们要的是最后一个 <= x 的位置，所以要往前退一格：
复杂度
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第二题：魔法石补给（考试版）
题意简化
有 n 种魔法石，第 i 种魔法石：
背包容量是 M，问最多能装出多少价值。
这是典型的完全背包。
为什么是完全背包
判断背包类型时，先看每种物品能选几次：
本题说每种魔法石可以使用任意多个，所以是完全背包。
状态设计
设：
一开始什么都不选：
对于第 i 种魔法石，如果当前容量 j 能放下它，那么有两种选择：
所以转移是：
完全背包的重点：容量要从小到大枚举。
因为从小到大枚举时，同一种物品刚刚更新出来的结果还可以继续被后面使用，这就实现了“同一种物品可以选很多次”。
参考代码
复杂度
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第四题：小码君买饮料 II
题意简化
有 n 种饮料，第 i 种饮料：
小码君至少要买到 L 的饮料量，问最少花多少钱。
注意关键词是“至少 L”，不是“刚好 L”。
部分分思路
N = 1
如果只有一种饮料，只能一直买这一种。
需要买的瓶数是：
在 C++ 中常用写法是：
答案：
所有 L[I] 都等于 1
如果所有饮料容量都是 1，那么买每一瓶都只增加 1 的容量。
要买到 L 的容量，就要买 L 瓶。
为了最省钱，每次都买价格最小的那种饮料。
答案：
L 较小
当 L 比较小的时候，可以直接做动态规划。
本题满分范围中 L <= 20000，其实也可以直接动态规划。
满分思路
这题也是完全背包，但是目标从“最大价值”变成了“最小花费”。
设：
但是题目要求“至少 L”，可能会买超过 L。
例如：
买一瓶就够了，虽然不是刚好 10。
一种常见写法是把容量最多算到 2L。
为什么算到 2L 就够？
所以读入每瓶饮料容量时，可以先写：
这样既能处理买超的情况，又不会把数组开得太大。
状态转移
一开始：
枚举每一种饮料，再枚举当前容量 j。
如果现在已经能花 f[j] 元买到 j 的容量，那么再买一瓶第 i 种饮料：
因为每种饮料可以买无限瓶，所以 j 从小到大枚举。
参考代码
易错点
不能只考虑刚好买到 L。
比如：
正确答案是 5，因为买一瓶就已经够了。
如果只做“刚好装满”，会认为无解，这是错误的。
复杂度
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第五题：沙漠商队补给（EASY）
题意简化
有 n 种补给，第 i 种补给：
背包容量是 M，问最多能获得多少价值。
这是多重背包。
部分分思路
C[I] = 1
如果每种物品最多只有 1 个，那么题目就变成了 01 背包。
枚举容量时要从大到小：
C[I] 比较小
如果每种物品数量很少，比如 c[i] <= 20，可以把同一种物品拆成很多个独立物品。
例如：
就当成 3 个普通的 01 背包物品。
这样容易写，但如果 c[i] 很大，会超时。
所有 W[I] 都等于 1
如果所有物品重量都是 1，那么背包最多能装 M 个物品。
这时应该优先拿价值大的物品。
做法：
满分思路：二进制拆分
多重背包的问题是：每种物品最多能选 c[i] 个。
如果直接一个一个拆，遇到 c[i] 很大就会很慢。
二进制拆分的想法是：把 c[i] 个物品拆成若干组，每组只能选 0 次或 1 次。
例如有 13 个同样的物品，可以拆成：
为什么这样拆？
因为：
用这些组，可以拼出从 0 到 13 的任意数量。
比如：
拆完之后，每一组就变成一个 01 背包物品。
如果一组代表 k 个原物品，那么它的：
然后做 01 背包即可。
为什么要限制可用数量
即使 c[i] 非常大，也不一定真的能用那么多个。
因为背包容量只有 M，第 i 种物品最多也只能放：
所以实际拆分前可以先写：
这样可以减少很多无用拆分。
参考代码
易错点
二进制拆分后，每一组只能用一次，所以容量必须从大到小枚举。
如果从小到大枚举，就可能让同一组被重复使用，数量限制会被破坏。
复杂度
每种物品会被拆成大约 log c[i] 组。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第六题：拯救OIBH总部
题意简化
有一个地图，地图中：
洪水会从地图外面流进来，只能经过 0，不能穿过 1。
问最后有多少个 0 不会被洪水淹到。
核心思路
洪水从外面来，所以只有和边界连通的 0 会被淹。
也就是说：
剩下没有被访问过的 0，就是安全区域。
这类题适合用 BFS。
算法步骤
1. 读入地图。
2. 把边界上的所有 0 加入队列。
3. 从这些边界 0 开始 BFS，把能到达的 0 全部标记为“会被淹”。
4. 最后遍历整张地图，统计没有被标记的 0。
参考代码
易错点
不要从内部的 0 开始搜索。
本题问的是“不会被外面洪水淹到的地方”，所以应该从边界开始搜索，先找出所有会被淹的地方。
复杂度
每个格子最多进队一次。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第七题：滑雪
题意简化
有一个 n * m 的高度地图。
从一个格子可以走到上下左右相邻的格子，但只能走到高度更低的格子。
问最长能经过多少个格子。
普通 DFS 为什么可能超时
如果从每个格子都直接 DFS，会有大量重复计算。
比如一个格子的答案已经算过了，别的起点走到它时，又会重新算一遍。
所以我们需要记忆化搜索。
状态设计
设：
如果 dp[x][y] 已经算过，就直接返回，不再重复搜索。
转移思路
从 (x, y) 出发，先至少能经过自己这个格子，所以：
然后尝试走向上下左右四个方向。
如果相邻格子 (nx, ny) 在地图内，并且：
说明可以滑过去。
那么答案可以更新为：
为什么不会死循环
因为每一步都必须走到更低的地方。
高度一直变小，不可能走一圈又回到原来的格子。
所以 DFS 是安全的。
参考代码
复杂度
每个格子的答案只会真正计算一次。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
第八题：炼金工坊升级
题意简化
有 D 轮实验，一开始有 M 点魔力。
每一轮有 n 种配方，第 i 种配方：
同一轮中，每种配方可以使用任意多次。
但是这一轮使用配方时，占用的总魔力不能超过当前拥有的魔力。
如果使用一次第 i 种配方，本轮结束后魔力的净变化是：
问经过 D 轮后，最多能有多少魔力。
先理解“一轮”在做什么
假设当前有 M 点魔力。
在这一轮里，每个配方可以看成一个物品：
本轮能占用的总魔力不能超过 M，这就像背包容量是 M。
目标是让本轮结束后魔力增加得最多，也就是让净收益最大。
所以每一轮其实都是一次完全背包。
为什么 R[I] <= C[I] 的配方通常不用
如果：
那么净收益：
使用它不会让魔力变多，甚至可能变少。
题目要求最大魔力，所以这种配方可以不选。
部分分思路
D、N、M 都很小
可以用动态规划或搜索尝试每一轮的选择。
不过只要理解成“每轮完全背包”，这个部分分也可以直接用满分做法通过。
N = 1
每轮只有一种配方。
如果这个配方不赚钱：
这一轮不做。
如果这个配方赚钱：
最多能做：
次。
本轮结束后：
每一轮最多只有一种赚钱配方
如果一轮里最多只有一种配方满足：
那么这一轮只需要考虑这一种赚钱配方。
处理方式和 n = 1 类似：
因为没有别的赚钱配方可以搭配。
D <= 30，N <= 30，M <= 20000
可以每一轮做一次完全背包。
这也是满分做法的核心。
满分思路
题目保证：
所以每一轮都开一个 f[0...M] 数组是可以接受的。
设当前轮开始时魔力是 M。
定义：
初始：
对于每个配方，如果它的净收益 r[i] - c[i] 是正数，就按完全背包转移：
容量从小到大枚举，因为同一种配方可以在同一轮使用多次。
这一轮结束后：
然后进入下一轮。
和普通完全背包的区别
普通完全背包通常是：
本题是：
也就是说，背包容量会随着轮数变化。
参考代码
样例解释
输入：
一开始有 10 点魔力。
第 1 轮：
当前容量是 10。
可以选择：
第 1 轮后：
第 2 轮：
当前容量是 14。
最优是配方 1 用 2 次：
最后：
答案是 20。
易错点
第一，不要把 r[i] 当成价值。真正增加的魔力是：
因为消耗的 c[i] 本来就要扣掉。
第二，每一轮的配方不同，所以每一轮都要重新清空 f 数组。
第三，完全背包容量从小到大枚举。
如果从大到小枚举，就会变成每种配方最多只能用一次，这是 01 背包，不符合题意。
复杂度
每一轮做一次完全背包。
其中题目保证 D * n <= 500，并且魔力不会超过 20000，所以可以通过。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
总结
这套题的核心不是代码很长，而是要先判断题型：
做题时建议先问自己三件事：
把题型判断对，代码就会顺很多。
