动态规划之【树形DP】第4课：树形DP应用案例实践3

动态规划之【树形DP】第4课树形DP应用案例实践3选课题目描述在大学里每个学生为了达到一定的学分必须从很多课程里选择一些课程来学习在课程里有些课程必须在某些课程之前学习如高等数学总是在其它课程之前学习。现在有N NN门功课每门课有若干学分分别记作s 1 , s 2 , ⋯ , s N s_1,s_2,\cdots,s_Ns1​,s2​,⋯,sN​每门课有一门或没有直接先修课若课程a aa是课程b bb的先修课即只有学完了课程a aa才能学习课程b bb。一个学生要从这些课程里选择M MM门课程学习问他能获得的最大学分是多少题目保证课程安排无冲突。即不会有a aa是b bb的先修课b bb也是a aa的先修课这类情况存在。输入格式第一行有两个整数N NNM MM用空格隔开( 1 ≤ N ≤ 300 (1 \leq N \leq 300(1≤N≤300,1 ≤ M ≤ 300 ) 1 \leq M \leq 300)1≤M≤300)。接下来的N NN行第i 1 i1i1行包含两个整数k i k_iki​和s i s_isi​k i k_iki​表示第i ii门课的直接先修课s i s_isi​表示第i ii门课的学分。若k i 0 k_i0ki​0表示没有直接先修课( 0 ≤ k i ≤ N (0 \leq {k_i} \leq N(0≤ki​≤N,1 ≤ s i ≤ 20 ) 1 \leq {s_i} \leq 20)1≤si​≤20)。数据保证至少存在一个k i 0 k_i0ki​0即至少一门课无先修课。输出格式只有一行选M MM门课程的最大学分。输入输出样例 1输入 17 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2输出 113思路分析题目是典型的“树形依赖背包”问题。每门课可能有先修课构成一个森林。为了方便我们添加一个虚拟根节点0将每个无先修课的课程作为0的子节点从而将森林转化为一棵以0为根的树。核心思想定义dp[u][j]表示在以u为根的子树中必须选修课程u的前提下总共选修j门课程能获得的最大学分。对每个子节点v进行 DFS递归得到dp[v][*]。合并子节点时采用分组背包的方式当前节点u已经处理了部分子树现在要将子节点v的选课方案合并进来。外层循环倒序遍历当前已选课程数j从大到小避免重复使用同个子树。内层循环枚举在子节点v中选修k门课k1因为选了u之后才能选v且v必须选才能获得dp[v][k]。初始状态dp[u][1] w[u]即只选自己。处理虚拟根00不是实际课程不消耗选课名额因此对它的所有子节点直接做分组背包dp0[j]表示在整棵树中选j门课的最大学分。最终答案即为dp0[m]。复杂度O(N * M^2)但由于子树大小限制实际运行效率较高N、M ≤ 300 完全可过。代码实现#includebits/stdc.husingnamespacestd;constintN305;// 最大课程数intn,m;// n: 课程总数, m: 要选的课程数vectorintg[N];// 邻接表g[i] 存储课程 i 的直接后继子节点intw[N];// w[i] 课程 i 的学分intsz[N];// sz[i] 以 i 为根的子树大小包含 iintdp[N][N];// dp[u][j] 以 u 为根的子树中强制选 u 且共选 j 门课的最大学分// 深度优先搜索计算以 u 为根的子树u 必须选的 DP 值voiddfs(intu){sz[u]1;// 初始化子树大小为 1只有自己dp[u][1]w[u];// 只选 u 一门课学分就是 w[u]// 遍历每个子节点 vfor(intv:g[u]){dfs(v);// 先递归处理子节点得到 dp[v][*] 和 sz[v]// 合并子节点 v 到 u 的背包中// 倒序枚举当前已经选了的课程数 j从 sz[u] 到 1// 因为要防止在本次合并中重复使用 v 的贡献for(intjmin(sz[u],m);j1;--j){// 枚举从子节点 v 中选 k 门课k 至少为 1因为选了 u 才能选 v// 且总课程数不能超过 mfor(intk1;ksz[v]jkm;k){dp[u][jk]max(dp[u][jk],dp[u][j]dp[v][k]);}}sz[u]sz[v];// 更新子树大小所有子节点合并完后才是真实大小}}intmain(){ios::sync_with_stdio(false);cin.tie(0);cinnm;for(inti1;in;i){intk,s;cinks;w[i]s;g[k].push_back(i);// k0 表示无先修课作为虚拟根 0 的子节点}// 对虚拟根 0 的每个子节点分别进行 DFSfor(intv:g[0])dfs(v);// 处理虚拟根 00 本身不是实际课程不占用选课名额// dp0[j] 表示在 0 的子树中选 j 门课的最大学分intdp0[N]{0};intcur0;// 当前已经处理过的子树的课程总数上限for(intv:g[0]){// 分组背包合并倒序枚举当前已选课程数 jfor(intjmin(cur,m);j0;--j){// 枚举从子节点 v 中选 k 门课k1for(intk1;ksz[v]jkm;k){dp0[jk]max(dp0[jk],dp0[j]dp[v][k]);}}cursz[v];}coutdp0[m]\n;return0;}功能分析1. 输入处理第一行两个整数N和M分别表示课程总数和需要选修的门数。接下来N行每行两个整数k i k_iki​和s i s_isi​ $k_i $ 是先修课编号0 表示无先修课s i s_isi​是学分。2. 核心功能将课程依赖关系构建成以 0 为根的树。通过树形 DP 分组背包计算出在满足先修依赖的条件下恰好选M门课能获得的最大总学分。3. 输出一个整数表示最大学分。4. 算法复杂度时间O(N * M^2)最坏情况约 300×300×300 ≈ 2.7e7常数较小可 AC。空间O(N * M)约 300×300 的 DP 数组。5. 关键点虚拟根简化森林为树统一处理。强制选当前节点保证依赖关系正确。分组背包合并每个子节点是一个“物品组”在组内只能选一种选法即选 k 门课。子树大小优化限制循环上界避免无效状态。完整系列资料请查看专栏《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;}