本文从WordPress迁移而来, 查看全部WordPress迁移文章
树dp
按点给出的顺序被点编号。“相邻”的点之间可以连一条边,最后得到的一棵树
题目是在树中找出一个连通的集合,使得点权最大(如果所有点都是负权,答案为0,即集合为空,不选任何点)
定1为根
设置状态:
dp[u][0]:在u所在子树中,不选点u的最优连通子集
dp[u][1]:在u所在子树中,选点u的最优连通子集
dp[u][0]:既然不能选u,那么连通子集必定来自于u下面的某个分支,而不可能跨越多个分支(否则必定经过u)
dp[u][0] = max( dp[v][0] , dp[v][1])
dp[u][1]:因为选了点u,可以连接不同的分支,但是要连一个分支的话,说明那个儿子必定要选,而且不是什么分支都连
只有大于0的才连,否则连上去要么不改变答案,要么令答案更小,肯定不是最优
dp[u][1] = sigma ( dp[v][1] ) dp[v][1] > 0
最后答案为 max(dp[1][0] , dp[1][1]);
1 |
|