树状DP
树上 DP#
树形 DP - OI Wiki (oi-wiki.org)
树状 DP:如名字所说,树状 DP 就是在树上做 DP,由于树的特殊性质,通过递归实现。
例题一 P1352 没有上司的舞会 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)题目大意:某大学有 n
个职员,编号为 1…n
他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数 r[i]
,但是呢,如果某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数。
使用 max(f[i][0/1])
来表示最优解,0
表示这个人不参加舞会的,1
表示这个人参加舞会的情况,于是有
注意:最后的结果为 max(f[1][0],f[1][1])
;
例题二 P 8625 [蓝桥杯 2015 省 B] 生命之树 - 洛谷 | 计算机科学教育新生态 (luogu. Com. Cn)
例题三 P 8744 [蓝桥杯 2021 省 A] 左孩子右兄弟 - 洛谷 | 计算机科学教育新生态 (luogu. Com. Cn)
树上背包#
P 2014 [CTSC 1997] 选课 - 洛谷 | 计算机科学教育新生态 (luogu. Com. Cn)题目大意: 现在有 n
门课程,第 i
门课程的学分为 a[i]
,每门课程有零门或一门先修课,有先修课的课程需要先学完其先修课,才能学习该课程. 一位学生要学习 m 门课程,求其能获得的最多学分数。
思路:本题集合了树形 dp 以及背包问题。一门先修课下面可能有多门其他课程,所以要使用背包来枚举选了哪几门课,然后再合并到先修课上,使用树状递归