问题求解III-HW07 题解

当遇到“最大化最小值”或者“最小化最大值”的问题时，二分答案 通常是将优化问题转化为判定问题的好思路。在这里我们检查二分答案适用的两个条件：

• 答案的离散有限性：该问题的答案必然为整数，且落在 $[1, \max(S)-\min(S)]$ 之间。
• 问题的单调性：如果我们找到一个方案满足答案 $d$，那么该方案也可以满足所以比 $d$ 更小的答案。

因此，我们可以在 $[1, \max(S)-\min(S)]$ 中二分答案 $mid$，每轮判断是否可以找到一个删除方案，使得最小的差值大于 $mid$。这一步可以通过贪心线性地判定：

• 如果存在一个最小差值大于 $mid$ 且不包含 $S$ 中最小数的方案，那么我们总可以将这个方案中的最小数换成 $\min(S)$，这个新方案只会比原方案更好。因此我们总是可以将 $\min(S)$ 作为构造方案中的最小数。
• 将 $S$ 中的数排序后，贪心地将数加入到方案中，用伪代码可以表示为

  current_max, count = S[0], 1
  for i in range(1, n):
    if S[i] - current_max >= mid:
        count += 1
        current_max = S[i]
  

• 最后检查贪心选中的数的个数是否大于等于 $n-k$ 即可。

每轮检查的复杂度为 $O(n)$，加上外层二分答案的复杂度，总时间复杂度为 $O(n\log \max(S))$。

本题旨在向大家展示树型动态规划基本的状态设计思想。令 $dp(u, 0/1)$ 表示考虑以 $u$ 为根的子树，$u$ 这个节点不选(0)/选(1)的情况下该子树内的最大权独立集权值，转移时考虑 $u$ 的所有孩子，确保不选中相邻的节点即可：

$$ \begin{align} dp(u, 1) &= \sum_{v\in son(u)}dp(v, 0) \\ dp(u, 0) &= \sum_{v\in son(u)}\max\{dp(v, 0), dp(v, 1)\} \end{align} $$

最终 $\max\{dp(Root, 0), dp(Root, 1)\}$ 即为答案。

状态的数目为 $O(n)$，所有状态转移的代价之和和树的边数的规模相同，也是 $O(n)$，因此该动态规划的总时间复杂度为 $O(n)$。