一类有依赖的树形DP

Text

这类问题通常形式是给定一棵树，父亲选了儿子才能选，求最优解或者方案数进行DP

考虑到如果直接枚举每一个儿子与父亲的转移，状态非常大，一般是难以跑过的

DFS序

对于树上的问题，可以考虑用DFS序来做。

我们知道一棵子树对应DFS序上的一段区间，区间的左端点是子树的根。

倒过来在DFS序上DP

设d[i]数组存dfs序

设F[i]表示DFS序上第i~N个已经做完了
如果d[i]这个点选，可以从F[i+1]转移过来

如果d[i]这个点不选，那么它整个子树都不能选，从F[i+size[d[i]]]转移过来

背包

经典的树上依赖背包问题是
给定一棵树，父亲选了儿子才能选，节点重量和价值，求有限重量下最大价值。

F[i][j]表示表示DFS序上第i~N个已经做完了，重量为j

可以从F[i+1][j-weight[d[i]]]+value[d[i]]、F[i+size[d[i]]][j]转移来

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!