使用魔法的先后没有影响。不妨先按 $a$ 排序。
不妨假设对集合 $S$ 使用魔法,那么 $S$ 可以把所有怪物清空的充要条件是:不存在 $i\not\in S$ 使得 $\sum_{j < i \lor j\in S} b_j< a_i$。即,比他大的且在集合中的人、在他前面的人都炸了他还炸不死。
如果 $b$ 是固定的,可以直接 dp。形如 $dp_{i,j}$ 表示考虑 $i\sim n$,选了 $j$ 个数的最大值。
然后 $b$ 不固定。我们要对 $S$ 钦定一些条件,使得满足条件的 $S$ 是最优且惟一的。经过手摸我们可以得到下面的条件:
- $S$ 要是合法的;
- 不存在 $i\in S,j\not \in S,i < j$ 使得 $b_i\leq b_j$(否则往后换)。
- 不存在 $i\not\in S,j\in S,i < j,b_i > b_j$ 使得 $S/\{j\}\cup\{i\}$ 仍然合法(否则交换,$\sum_{i\in S} b_i$ 变大)。
- 不能去掉 $S$ 中任意元素,$S$ 仍然合法。
直接 dp 即可。