树形背包 — Luogu P1273 有线电视网
2018年10月09日 / 周二 / 0
条评论
0x01 写在开头
题目链接:[https://www.luogu.org/problemnew/show/P1273]
前置技能 : 树形DP
如果做过选课的话,想必各位一看到就知道这是一道树形DP的题目
0x02 题目
题目中要求我们在以收入$\geq 0$的前提下,支持尽可能多的叶子节点
因此我们可以这么定义一个类似背包状态转移方程
$$
f(now,i+j)=m ...