10162. 「一本通 5.2 练习 5」骑士

题意

有$n$个骑士,每个骑士有一个自己的战斗值,每个骑士也有且仅有唯一一个自己讨厌的骑士,每个骑士不可能与自己讨厌的骑士一起上场战斗,问最高的战斗值之和是多少?

思路

这道题与没有上司的舞会很像。但是注意,这道题可能会有环的存在,所以我们需要对于每个环,把它切割成两部分,再分别树形dp,然后取最大值,加入ans中。 树形dp的思路很简单: 设$f[x][0]$表示第$x$个骑士不上战场。 设$f[x][1]$表示第$x$个骑士上战场。 那么很简单就可以推出: $$f[x][0]=\sum{max(f[to][0],f[to][1]),to∈son_x}$$ $$f[x][1]=a[x]+\sum{f[to][0],to∈son_x}$$
暂无评论

发送评论


				
上一篇
下一篇