本文从WordPress迁移而来, 查看全部WordPress迁移文章
树dp
题意:给一颗无根树,每个点有权值,要找出一个子树,点数为m,并且使得m个点的权值和最小。
定1为根
定义dp[u][m],以u为根的子树下,包含m个点的最小权值。因为每个点都可能作为最后那个子树的根,所以枚举所有的dp[u][m],找出最小的那个值
ANS = min(dp[u][m]);
考虑转移,因为是以u为根的子树,所以u这个点是必须选的,然后考虑u下面的子树怎么选,这就是个背包问题。u下面的第1个子树选了k1个点,第2个子树选了k2个点,第3个子树选了k3个点…..最后使得总权值和最小
dp[u][m] = min(dp[u][m] , dp[u][m-i] + dp[v][i]);
1 |
|