树形依赖背包

例题

有 $n$ 门课，每门课程有不同的学分，都可能有一门或没有需要先修的课程。求在 $m$ 门课的前提下，能够获得的最大学分是多少。

想选一个课程，必须先选它的父亲。设 $f_{i,j}$ 为在以 $i$ 为根的子子树中，选 $j$ 个点能获得的最大学分。那么可以枚举父亲和儿子的 $j$ 进行转移，再求出子树大小进行优化，复杂度 $O(n^2)$

void dfs(int x, int fa) {
sz[x] = 1;
for (int i = head[x]; i; i = e[i].nxt) {
int y = e[i].to;
if (y == fa) continue;
dfs(y, x);
memset(g, 0, sizeof(g)); //g 一定要初始化
for (int j = sz[x]; j; j--) // 一定要反响枚举，避免后效性
for (int k = sz[y]; k; k--)
g[j + k] = max(g[j + k], f[x][j] + f[y][k]);
sz[x] += sz[y]; // 注意这行代码的位置
for (int j = 1; j <= sz[x]; j++) f[x][j] = max(f[x][j], g[j]);
}
}

• 关于转移的枚举，这个顺序最好别改，可能改错。比如下方代码，当 $j=1,k=1$ 时，只能选 $x$。但可能取的是 $y$ 而不是 $x$。

for (int j = sz[x]; j; j--)
for (int k = sz[y]; k > 0; k--) {
if (j - k < 1) continue;
f[x][j] = max(f[x][j], f[y][k] + f[x][j - k])
}

• 关于 $g$ 数组的作用。比如 $i$ 和 $j$ 都枚举 $1,2$。假设 $1$ 和 $1$ 更新了 $f$。然后枚举到了 $2,1$，那么会用到被更新的 $f$，那么儿子中的点被算了两次。

最后

以上就是包容山水最近收集整理的关于树形依赖背包的全部内容，更多相关树形依赖背包内容请搜索靠谱客的其他文章。