题解 AT4120 【[ARC096D] Sweet Alchemy】

· · 题解

PS：主要是想补充最后贪心正确性的证明

首先差分，问题变为每次选择一棵子树，权值为 sz，花费为 \sum m_i，且除了1号点的子树最多选 d 次。

直接背包的话，因为权值和花费都很大，无论哪种状态都没法做。

考虑到 n 很小，我们有一种复杂度与权值和花费都无关的选物品方法：贪心，尽可能选择性价比大的物品。 直接贪心不对，我们考虑贪心能在什么情况下适用： 设 i,j 两个物品的权值分别为 v_i,v_j，且权值比 \frac {v_i}{w_i}<\frac {v_j}{w_j}，那么如果 i 选了 v_j 个物品，就可以替换为 j 选 v_i 个物品，权值不变，花费变小，此时按贪心的顺序选是对的。

所以可以把 \min(d,\max v_i) 个物品拿来做背包，剩下的部分贪心选择。因为权值最大是 sz=n，可以设 f[i] 表示权值和为 i 时的最小花费，然后枚举一个权值，剩下的花费贪心选择。 复杂度 O(n^3*n\log n+n^4)，权值和的范围是 n^3。

贪心的正确性可以这么理解： 在最优解中，如果最终 j 的个数剩下 \ge n 个，i 选的个数一定 \le n，当我们背包确定了 i 在 n 以内选多少个时，剩下的花费就按顺序先给 j 贪心选，能够取到最优解。 如果最终剩下 j 的个数 x<n 个，那么背包确定选 n-x 个，剩下的 d-n 个贪心会全部选满（因为贪心的最大个数是 d-n，不会再去取那 x 里面的），此时恰好能够取到最优解，而不会出现 j 的贪心错误地占据了后面的花费的情况。