本文从WordPress迁移而来, 查看全部WordPress迁移文章
树dp
题意:给一个n个点的无根树,给一个长度L,要找出一条长度不超过L的链(即点数不超过L+1),然后其他点要汇聚到这条链上(每个点选链上离它最近的点),求其余点走到链上的距离和。问要怎么选这条链,然后使得这个距离和最小。
这个题目挺难的,难的部分个人觉得是在实现部分,想到了也不好实现,另外,怎么设置状态也是关键的,状态设置好了,复杂度能降维
分析:定0为根,然后,既然是要我们找一条长度不超过L的链,那怎么找?可以枚举树中的每个点u,假设这个点在链上,并且这条链是向下垂的,也就是这条链在u子树下,那么这条链的形状可以是”|”或者”^”,即可以看成又1条组成的或者2条组成。这样枚举,可以做到不遗漏所有情况,也不做多余的枚举。
假设我们已经得到了一条链,要怎么计算出其余点到这条链上的距离和呢?这需要dp记录一些信息
downcost[u],u下面的子树全部回到u的花费
upcost[u],u上方的所有点全部回到u的花费
cnt[u],u下方有多少个点
up[u],u上方有多少个点
downcost[u] = sigma downcost[v] + (cnt[u]-1);
upcost[u] = upcost[fa] + up[fa] + downcost[fa] - (cnt[fa]-1) - downcost[u] + 2*(cnt[fa]-1-cnt[u]) + 1;
cnt[u] = sigma cnt[v] + 1;
up[u] = n - cnt[u];
得到这些信息是为了dp转移的时候可以用上
定义dp[u][m]:选了点u,且在u子树下找到一条长度不大于m的链,其他点汇聚过来的最小花费,注意这里的链一定是直线”|”而不是叉链”^”
dp的定义可以看出,它是可以继承上一次的答案的,因为是“不大于m的链”
dp[u][m] = min(dp[u][m-1] , downcost[u] - downcost[v] - cnt[v] + dp[v][i-1]);
然后就是怎么更新答案了
最后要找的链如果是”|”的,可以直接由dp[u][m]的信息得到
如果是”^”的话,需要两条儿子链组成
假设链上的点数不超过m,那么u用掉一个点,下面dp[v1][k],dp[v2][m-1-k],这样就形成了”^”
这里就需要枚举两个儿子v1和v2?不用了,我们限定了顺序的话,一直枚举一直更新,只需要枚举一个儿子即可
选了v1和v2的话,花费就是
upcost[u] + downcost[u] + dp[v1][i-1] - downcost[v1] - cnt[v1] + dp[v2][i-1] - downcost[v2] - cnt[v2]
这里的实现有些讲究,可以降低复杂度
1 |
|