观赏题目
文明观题,静止内卷(bushi
题目描述
在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程之前学习。现在有N门功课,每门课有个学分,每门课最多只有一个直接先修课,每门课可是最多两门其它课程的直接先修课(若课程a是课程b的先修课即只有学完了课程a,才能学习课程b)。一个学生要从这些课程里选择M门课程学习,问他能获得的最大学分是多少?
输入格式
第一行有两个整数N ,M用空格隔开。(1$\le$N$\le$200,1$\le$M$\le$150)
接下来的N行,第I+1行包含两个整数ki和si, ki表示第i门课的直接先修课,si表示第I门课的学分。若ki=0表示没有直接先修课(1\(\le\)ki\(\le\)N, 1\(\le\)si$\le$20)。
数据保证只有一门课程ki=0
输出格式
只有一行,选M门课程的最大得分。
样例数据
样例输入
5 3
3 5
5 18
5 2
3 10
0 7
样例输出
27
思路分析
先修课?树?
容易发现,在这里我们α是β的先修课这个关系可以构成一颗树,我们可以像没有上司的舞会的思路来通过找根节点对其子树进行遍历
遍历?D/BFS?
在这里,建议使用DFS,因为每个根节点都会用到ta的所有子节点的局部最优解
最优解?DP?
考虑到最优解,又不禁联想到了这个 万恶不赦 的树形DP,这道题也确实可以用DP来解决
DP?珂爱的状态?
接下来,我们考虑一下这个十万恶不赦的状态
原文地址:http://www.cnblogs.com/Random-life/p/16926688.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性