SGU 195 New Year Bonus Grant

题意

某厂采用一种奇怪的方式发奖金,给出一个上下级关系树,大BOSS是1号根节点,别的员工都有自己的上司。对于每个员工,它有三种选择,要么接受上级下发的奖金,要么给所有下级发奖金,要么啥都不做(只有傻子才会这样,所以你可以当成没这种选择),大BOSS一定发奖金。只要一个员工选择收奖金,他就得到1000块。

现在要你设计一种方案,使得所有人收到的奖金的总数额最大。

思路

树DP解法

对于每一个节点,都有两种状态:选择收奖金,选择收奖金。

对于选择收奖金的节点的儿子节点,一定不可以选择收奖金。

对于选择发奖金的节点的儿子节点,可以选择收他的奖金,也可以选择发奖金。

这样就可以建立dp数组dp[a][0/1],a是节点对应的编号,0/1表示该节点选择收/发奖金的状态。利用DFS下潜到叶子节点之后,就可以开始树DP了。

状态转移的方程可以参考dfs()方法。

输出路径的话,只要记录下每一次的决策,DP结束之后反查就可以搞定。

贪心解法

引用自JHC23的Blog。

自底而顶遍历,如果自己的上级没有接受奖金(那么就能够把钱给发自己了),而自己也从不增接受奖金则可以获得奖金,同时标记自己和上级。这样下去就可以得到可得到最大奖金。

代码

树DP解法:

 

Leave a Reply

Scroll to top