重做 [SDOI/SXOI2022] 小 N 的独立集

· · 个人记录

当年连树背包复杂度是 \Theta(n^2) 都不知道的我在考场上还在快乐地扒拉出题人爬，属实小丑。

一眼丁真，鉴定为 dp 套 dp。直接设 dp_{x,i,j} 表示 x 的子树中一定不选 x 的最大独立集大小为 i，一定选 x 的最大独立集大小为 j 的方案数，用二维背包转移，时间复杂度 \Theta(n^3k^4)。

考虑压缩状态。考虑内层 dp，f_{x,0/1} 为是否选择 x 时的最大独立集，转移为 f_{x,0}=\max(f_{v,0},f_{v,1}),f_{x,1}=f_{v,0}+1。不难发现，当 f_1 \leq f_0 时，转移只有 f_0 在起作用，所以我们不妨令 f_1=f_0。当 f_1 > f_0 时，考虑不选点 x，则 f_0 \geq f_1-k。综上所述，有 f_0 \leq f_1 \leq f_0+k。

考虑把状态的意义改为 x 的子树中一定不选 x 的最大独立集大小为 i，一定选 x 的最大独立集大小比前者大 j 的方案数。 树形背包转移，时间复杂度 \Theta(n^2k^4)，看似跑不过实则飞快。