本文从WordPress迁移而来, 查看全部WordPress迁移文章
树dp + 背包思想
如果能想明白一个最优性的问题,就能理解为什么跟背包联系在一起
对于以u为根(包括u)的子树,如果派了k个机器人下去,注意这里k >= 2
那么没有一个机器人会再从u这里跑出来!
如果是派了1个机器人下去,那么有可能不再出来了,也可能会重新出来
为什么在k>=2的时候不会再跑出来了?
假设k个进去,有一个出来,称出来的机器人为x,那么x至少走了一条路径进去,然后又走出来
(即至少一条路径被重复走了),那么这条重复的路径,完全可以由其他的机器人代劳,不必要x去走重复的
也就是说,与其派k个下去,让其他一个走了重复路径,不如派k-1个下去,能做到同样的效果
而多出来的那个,从fa到u要花费,从u离开到fa也要花费,显然不是最优
所以定义的dp状态为,dp[u][k],派k个机器人下去u的子树(并且这k个机器人不会再离开u)的最小花费
那么目标状态就是dp[S][K]
dp[u][k] = min(dp[u][k-kk] + dp[v][kk] + kk * w);
特别的,dp[u][0],表示的其实是派了1个机器人下去u的子树走遍了整个子树再回到u
1 |
|