Solution - P4516 [JSOI2018] 潜入行动

P4516 [JSOI2018] 潜入行动

大体思路就是设 $f(x,i,j,h)$ 表示以 $x$ 为根的子树中放 $i$ 个，其中 $j$ 表示 $x$ 节点上放不放， $h$ 表示 $x$ 节点有没有被子节点干掉的方案总数。

然后就可以跑个分组背包，发现转移是 $O(k^2)$ 的。

然后有个很牛逼的道理就是均摊复杂度是 $O(n\cdot k)$ 的（待研究）。

然后这道题教会了我两个东西：

1. 当转移涉及自身时（即物品的体积可以为 $0$ ），千万不能倒序转移，一定要写滚动数组（不然就会在同一节点上累加多次）。

2. 查表法（填表法）：每次确定需要转移的状态，往前面找状态转移。
   刷表法：每次确定一个状态，转移到后面的状态。
   很多时候我用的都是第一种，但是在树形背包中，用第一种会多转移很多状态，使复杂度假掉。换成刷表法才能 AC 。