Description

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有N门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程a是课程b的先修课即只有学完了课程a，才能学习课程b）。一个学生要从这些课程里选择M门课程学习，问他能获得的最大学分是多少？

Input&&Output

input

第一行有两个整数N,M用空格隔开。(1<=N<=300,1<=M<=300)

接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课，si表示第I门课的学分。若ki=0表示没有直接先修课（1<=ki<=N, 1<=si<=20）。

output

只有一行，选M门课程的最大得分。

Sample

Sample Input

7  4

2  2

0  1

0  4

2  1

7  1

7  6

2  2
Sample Output

13

题解

为什么都用dfs 拓扑序多好用2333

首先我们把k==0的课程 的先修课 当作课程0

然后对每个点往它的先修课连一条边 会形成一棵以0为根的树形结构

对每个点记录它连出边的终点编号（to[ x ]）和它的入度(rd[ x ])
然后就可以按拓扑序dp了

记f[i][j]为 在i号点 选了i的子树上（一定包括i 共j个点 最多能拿到的学分

然后跑01背包 转移方程：f[to[x]][i]=max(f[to[x]][i],f[to[x]][i-j]+f[x][j]);

最后结果在f[][m+]上
 #include<iostream>

 #include<cstdio>

 #include<queue>

 #include<cmath>

 using namespace std;

 #define R register

 int f[][];

 int to[];

 int rd[];

 queue<int>q;

 int main()

 {

     int n,m;

     scanf("%d%d",&n,&m);

     for(R int i=;i<=n;++i)

     {

         scanf("%d%d",&to[i],&f[i][]);

         rd[to[i]]++;//终点入度++

     }

     for(R int i=;i<=n;++i)

     if(!rd[i])q.push(i);

     while(!q.empty())

     {

         int x=q.front();q.pop();

         for(R int i=m+;i>=;--i)

         for(R int j=i-;j>=;--j)

         f[to[x]][i]=max(f[to[x]][i],f[to[x]][i-j]+f[x][j]);//01背包

         //

         rd[to[x]]--;

         if(!rd[to[x]])q.push(to[x]);

     }

     cout<<f[][m+];

     return ;

 }

最新文章

  1. 解决xcode8模拟器不能删除应用的问题
  2. int(*f)(int)
  3. OCP笔记001
  4. iOS 第三方自定义Alertview项目MBProcessHud中的重要代码分析
  5. [SAP ABAP开发技术总结]权限对象检查
  6. latex figure \label 放在\caption 后
  7. [工作积累] OpenGL ES3.0: glInvalidateFramebuffer
  8. 怎么手写Ajax实现异步刷新
  9. Tomcat的server.xml(中文版)
  10. oracle的安装与plsql的环境配置
  11. c#下载文件案例
  12. sql数据库删除表的外键约束（INSERT 语句与 FOREIGN KEY 约束&quot;XXX&quot;冲突。该冲突发生于数据库&quot;XXX&quot;，表&quot;XXX&quot;, column &#39;XXX）
  13. configure文件的生成
  14. Linux-004-解决 Tomcat 启动时提示 Insufficient space for shared memory file
  15. C16记技术服务支持
  16. 【CSS】Sticky Footer 布局
  17. Django的rest_framework的分页组件源码分析
  18. python 最简单的爬虫
  19. 【Linux】编辑文件时，箭头按键还有BACKSPACE按键不能正常使用的解决办法
  20. SpringMVC之ajax+select下拉框交互常用方式

热门文章

  1. Neo4j 第六篇：Cypher语法
  2. codevs科技庄园
  3. cms完整视频教程+源码 孔浩老师 全131讲
  4. BUPT复试专题—最长连续等差子数列(2014软院)
  5. CSS3绘制灰太狼动画，绝对精彩
  6. android 文件读取（assets）
  7. HDU2489 Minimal Ratio Tree 【DFS】+【最小生成树Prim】
  8. Struts2+Spring+Hibernate step by step 04 整合Spring之二，从数据库验证username和password
  9. SGU 194 Reactor Cooling 无源汇带上下界可行流
  10. 翻译：A Tutorial on the Device Tree (Zynq) -- Part III