P9378 [THUPC 2023 决赛] 物理实验

为了验证新提出的猜想，物理学家小 I 需要完成 $n$ 种物理实验，其中第 $i(1 \le i \le n)$ 种实验的重要度是 $2^{-i}$。每种实验仅需要完成一次。小 I 一次只能做一种实验，且在开始了一个实验之后，不能做到一半去做另一个实验，也就是说在没有任何其他限制的情况下，小 I 完成实验的顺序可以用一个 $1$ 到 $n$ 的排列表示。 然而事情并非一帆风顺。有 $m$ 轮宇宙射线，分别会在小 I 完成了 $a_1$ 种、$a_2$ 种、$\dots$、$a_m$ 种（**注意，不是第 $a_i$ 种**）实验后轰击实验基地，保证 $1 \le a_1 < a_2 < \dots < a_m < n-m$。因此小 I 需要仔细地安排实验的顺序。 第 $j(1 \le j \le m)$ 轮宇宙射线会恰好干扰一种实验的实验仪器，其干扰的实验种类按照以下方式确定： - 给出一个 $1$ 至 $n$ 的排列 $p_{j,1},\dots,p_{j,n}$，其中 $i$ 越靠前表示第 $i$ 种实验对这轮宇宙射线越脆弱。**每轮给出的排列不一定相同。** - 那么在这轮宇宙射线轰击实验基地时，目前所有**未完成且未被干扰**的实验中最脆弱的一种会被干扰，之后无法进行对应实验。 在以上条件下，小 I 总共可以完成 $(n-m)$ 种实验。小 I 希望它们的重要度总和尽可能大，可是小 I 是物理学家不懂算法，所以小 I 请教于你。你需要给出合理的实验顺序，使得完成的 $(n-m)$ 种实验均未被宇宙射线干扰且重要度总和尽可能大。

无

无

**【样例解释 #1】** 小 I 第一次完成第一种实验后，宇宙射线将会轰击第二种实验的仪器，因此第二次只能完成第三种实验。容易证明该方案达到最大重要度。 **【样例解释 #2】** 在这个样例中，如果小 I 第一次完成第一种实验，那么宇宙射线将会轰击第二种实验的仪器，导致第二次只能完成第三种实验。此时重要度为 $0.625$，而样例输出给出的方案重要度为 $0.75$。 **【样例解释 #3】** 该组样例有多个合法的输出，如 `5 4 1 2` 也是一个合法的答案。 **【数据范围】** 对于所有测试数据，$3 \le n \le 600$，$1 \le m \le \lfloor \frac{n-1}{2} \rfloor$，$1 \le a_1 < a_2 < \dots < a_m < n-m$。 **【题目来源】** 来自 2023 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2023）决赛。 题解等资源可在 [https://github.com/THUSAAC/THUPC2023](https://github.com/THUSAAC/THUPC2023) 查看。