QOJ.ac

QOJ

Type: Editorial

Status: Open

Posted by: ucup-team3407

Posted at: 2026-01-13 16:27:30

Last updated: 2026-01-13 16:49:13

Back to Problem

题解

使用魔法的先后没有影响。不妨先按 $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 即可。

Comments

No comments yet.