树形dp的学习
很烦啊,最近复习图论,贼艰难,很多题目基本多多少少都要用树形dp。而我专注于搞图论和数据结构,dp完全就是略知一二,逃避没有用,不会就去学,碰到困难就去面对。
树上dp其实跟普通的dp差不多,甚至会比普通的dp写起来简单,但是前提是要理解。
例题
洛谷P1352这个真的是典中典了,我看几乎所有的技术博客都会拿这个当作树形dp的入门题,那我也不例外。
题目分析
某大学有 \(n\) 个职员,编号为 \(1\ldots n\)。
他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。
现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数 \(r_i\),但是呢,如果某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。
所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数。
其实我觉得这个跟有依赖的背包题有异曲同工之妙,不通的是,他们不是依赖,而是互斥,选了一个人之后则不能选另一个人。而依赖背包则是选了一个则必须选另外一个,当然另外一个没有这个限制,否则两个物品直接合并一个物品啦。
这里很明显就是 \(n\) 个人 \(n-1\) 对关系,可以算做一棵树,但是这棵树是有向的,最顶级的那个上司就是树根了。这里我们肯定得先建一个有向图来保存这个关系,然后我们需要自底向上分析策略。对于每一个叶子节点,它们没有下级,对他们来说只有参加或者不参加,这里我们设 \(dp[i][0]\) 为第 \(i\) 个人不来参加的最优解,\(dp[i][1]\) 为第 \(i\) 个人来参加的最优解,注意这个最优解是对于它以及它的所有子孙节点的最优解。我们假设节点 \(i\) 有k个节点分别为 \(a_1,a_2\dots a_k\) ,那么可以写出如下状态转移方程。
\(dp[i][1] = \sum _{x=1} ^{k} dp[a_x][0]\)
\(dp[i][0] = \sum _{x=1} ^{k} \max(dp[a_x][0],dp[a_x][1])\)
这里很明显,对于本人不参加,那么自己的下属可参加可不参加,但是自己参加了自己的下属一定不能参加,而自己不参加选择下属参加还是不参加也是选取最优结果的,因此能得到上面的状态转移方程。然后就是最基本的树的操作了:建边,找根,dfs,状态转移,最后结果就是 \(\max(dp[root][1],dp[root][0])\),所以这道题是真的入门题。
标程
1 |
|