P15819 [JOI 2015 Final] 舞会 / Ball 题解

建议降蓝。

首先编号显然是不重要的，因为最后只让最大化权值。其次具体权值也是不重要的，因为我们只对权值进行比较，只关心它们之间的大小关系。另外这个所谓的队列其实是一个三叉树的结构，下文将在树形上讨论。

直接做是困难的，容易想到二分答案转判定。设答案 ，那么我们把权值 的视为 ，权值 的视为 ，可以先把确定的权值填到树上，我们的目标是让根节点成为 。由题意可知，一个节点是 当且仅当它至少有两个儿子是 。我们显然不能把 视作 ，否则答案会变大，这说明 的数量是有限的，我们要在让根成为 的同时最小化叶子中 的数量。如果最后 没用完，我们将它视作 即可，并不影响答案。需要注意的是，若一个叶子已经被确定为 ，那么它不能被视为 ，否则会多出一个 ，我就因为这个挂的 /ll。

考虑如何最小化叶子中 的数量。设 表示 是 时，它子树内 未确定的叶子 中 的数量的最小值，有：

• 若 是叶子：
  • 若 的权值已经确定：
    • 若 ，那么 。
    • 若 ，那么 。
  • 若 的权值还未确定，那么 。
• 若 不是叶子，那么 是它的三个儿子的 值中较小两个的和。

DP 完成过后，只需要统计一下一共有多少个未确定的权值 的位置即可。时间复杂度 。