动态规划之【树形DP】第1课：通过一个案例深入浅出研究树形DP

动态规划之【树形DP】第1课通过一个案例深入浅出研究树形DP一、 什么是树形DP树形DP是在树这种数据结构上进行的动态规划。由于树具有天然的递归性质每个子树都是一棵树因此通常使用递归DFS来实现。二、 基本特点状态定义通常以dp[u][...]表示以节点 u 为根的子树的相关信息转移方式从子节点向父节点转移后序遍历时间复杂度通常为 O(n) 或 O(n × k)其中 k 是状态维度三、 常见题型分类树的最大独立集选或不选节点的问题树形背包在树上做分组背包树的直径树上最长路径换根DP需要计算每个节点作为根时的答案树上路径问题统计路径数量等研究案例没有上司的舞会题目描述某大学有n nn个职员编号为1 … n 1\ldots n1…n。他们之间有从属关系也就是说他们的关系就像一棵以校长为根的树父结点就是子结点的直接上司。现在有个周年庆宴会宴会每邀请来一个职员都会增加一定的快乐指数r i r_iri​但是呢如果某个职员的直接上司来参加舞会了那么这个职员就无论如何也不肯来参加舞会了。所以请你编程计算邀请哪些职员可以使快乐指数最大求最大的快乐指数。输入格式输入的第一行是一个整数n nn。第2 22到第( n 1 ) (n 1)(n1)行每行一个整数第( i 1 ) (i1)(i1)行的整数表示i ii号职员的快乐指数r i r_iri​。第( n 2 ) (n 2)(n2)到第2 n 2n2n行每行输入一对整数l , k l, kl,k代表k kk是l ll的直接上司。输出格式输出一行一个整数代表最大的快乐指数。输入输出样例 #1输入 #17 1 1 1 1 1 1 1 1 3 2 3 6 4 7 4 4 5 3 5输出 #15数据规模与约定对于100 % 100\%100%的数据保证1 ≤ n ≤ 6 × 10 3 1\leq n \leq 6 \times 10^31≤n≤6×103− 128 ≤ r i ≤ 127 -128 \leq r_i\leq 127−128≤ri​≤1271 ≤ l , k ≤ n 1 \leq l, k \leq n1≤l,k≤n且给出的关系一定是一棵树。思路分析题目理解树结构职员之间的从属关系构成一棵树父节点是子节点的直接上司。约束如果某个职员参加舞会则其直接下属不能参加。目标在满足约束的前提下使得参加职员的快乐指数总和最大。状态定义设dp[u][0]表示以u为根的子树中不邀请 u时能获得的最大快乐指数dp[u][1]表示以u为根的子树中邀请 u时能获得的最大快乐指数。转移方程若邀请u则其所有直接下属都不能邀请因此dp[u][1] r[u] Σ dp[v][0]v是u的子节点。若不邀请u则其每个下属可以邀请或不邀请取较大值因此dp[u][0] Σ max(dp[v][0], dp[v][1])。实现步骤读入n和每个职员的快乐指数r[i]。读入n-1条边(l, k)表示k是l的直接上司因此建边方向为k → l。同时记录每个节点是否有父节点从而找到根节点没有父节点的节点。从根节点开始 DFS按照转移方程计算 DP 值。最终答案 max(dp[root][0], dp[root][1])。复杂度时间复杂度O(n)每个节点访问一次。空间复杂度O(n)存储邻接表和 DP 数组。代码实现#includebits/stdc.husingnamespacestd;constintN6010;intn,r[N],f[N][2];vectorinte[N];boolfa[N];// 标记是否有父节点voiddfs(intu){f[u][0]0;// 不邀请 u 的初始快乐值f[u][1]r[u];// 邀请 u 的初始快乐值for(intv:e[u]){dfs(v);f[u][1]f[v][0];// u 邀请 - 子节点都不能邀请f[u][0]max(f[v][0],f[v][1]);// u 不邀请 - 子节点可选最优}}intmain(){cinn;for(inti1;in;i)cinr[i];for(inti1;in;i){intl,k;cinlk;e[k].push_back(l);fa[l]true;// l 有父节点}introot1;while(fa[root])root;// 找到根节点无父节点dfs(root);coutmax(f[root][0],f[root][1])endl;return0;}功能分析建树根据输入的(l, k)边建立有向邻接表同时记录每个节点的父节点信息最终定位根节点。DFS 遍历从根节点开始递归处理每个子树按照树形 DP 的转移方程自底向上计算两种状态下的最大快乐值。结果输出取根节点两种状态的最大值即为全局最大快乐指数。完整系列资料请查看专栏《csp信奥赛C动态规划》https://blog.csdn.net/weixin_66461496/category_13096895.html各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}