hdu 1520 Anniversary party (树形dp模板题)

题目链接
题意:一个舞会,每个人有一个val,给出n个人之间的领导和被领导关系,一个人不愿意与他的领导同时参加,问一种安排方案,使得参加的人的val和最大,问这个最大的和是多少。

思路:树形dp模板题。

dp1[v]表示包含v节点的子树的最大值。

dp2[v]表示,不包含v节点的子树的最大值。

下面讲得很清楚。。

Now, similar to array problem, we have to make a decision about including node V in our subset or not. If we include node V, we can’t include any of its children(say v1, v2, …, vn), but we can include any grand child of V. If we don’t include V, we can include any child of V.

So, we can write a recursion by defining maximum of two cases.
.

As we see in most DP problems, multiple formulations can give us optimal answer. Here, from an implementation point of view, we can define an easier solution using DP. We define two DPs, and , denoting maximum coins possible by choosing nodes from subtree of node V and if we include node V in our answer or not, respectively. Our final answer is maximum of two case i.e. .

And defining recursion is even easier in this case. (since we cannot include any of the children) and (since we can include children now, but we can also choose not include them in subset, hence max of both cases).

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz