poj 2342 Anniversary party (基础树形dp)

题目链接

题意:n个人的上下级关系形成一棵树..每一个人有一个val(可正可负),要选若干个人参加一个party,要求是一个人和他的直接上级不能同时在场。问参加party的人最大的val之和。

思路:树形dp入门题。

 

dp[i][0]和dp[i][1]分别表示第i个人不参加和参加party对应的val和。

注意dp转移方程是放在每次dfs之后的回溯位置的。。。

这样做的话访问是从根节点到叶子节点,更新就成了从叶子节点到根节点。。。

联想到数字三角形…其实是一样的。。

sad…dp苦手如我也开始刷dp了吗。。。。

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz