Luogu 2014 – 选课

题目链接:洛谷 P2014

树上背包问题。$f(u,x)$表示以$u$为根的子树中选择$x$个节点的最大收益,其中$u$是必选的。那么$f(u,x) = \max \{ f(u, x – k) + f(v, k) \}$,其中$v$是$u$的儿子。我们观察到$k$应当满足$1 \leq k \leq \min \{ {\rm size}(v), x – 1 \}$。初始化$f(u,1) = s_u$。

观察这个状态转移方程,我们可以理解第一维$u$是树形DP维,第二维是背包问题的容积维,那么我们在DP的时候对第一维进行DFS,对第二维倒序枚举(参见滚动数组优化01背包)。

 

说点什么

avatar
50
  Subscribe  
提醒