大学实行学分制。每门课程都有一定的学分，学生只要选修了这门课并通过考核就能获得相应学分。学生最后的学分是他选修各门课的学分总和。
每个学生都要选择规定数量的课程。有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其他的一些课程基础上才能选修。例如《数据结构》必须在选修了《高级语言程序设计》后才能选修。我们称《高级语言程序设计》是《数据结构》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述，每门课都有一个课号，课号依次为 1,2,3,⋯。
下面举例说明：
| 课号 | 先修课号 | 学分 |
|---|---|---|
| 1 | 无 | 1 |
| 2 | 1 | 1 |
| 3 | 2 | 3 |
| 4 | 无 | 3 |
| 5 | 2 | 4 |
上例中课号 1 是课号 2 的先修课，即如果要先修课号 2，则课号 1 必定已被选过。同样，如果要选修课号 3 ，那么课号 1 和 课号 2 都一定被选修过。
学生不可能学完大学开设的所有课程，因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。请找出一种选课方案使得你能得到的学分最多，并满足先修课优先的原则。假定课程间不存在时间上的冲突。
输入格式
输出格式
样例
数据范围与提示
做这道题的时候脑子也不清醒...
这都怪教主的歌（顺便说一句新歌Darkside超好听）
背包对我就是个巨坑...哎 接着好好学吧
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int MAXN = 1e7 + 5 ; 5 6 int n , m , a , b , c , k ; 7 int value[1001] , next[1001] , to[1001] , head[1001] , tot[1001]; 8 int f[1001][1001] ; 9 bool vis[1001] ; 10 11 int read(){ 12 char c ; 13 int sign = 1 ; 14 while((c = getchar()) < '0' || c > '9') 15 if(c == '-') sign = -1 ; 16 int Ans = c - '0' ; 17 while((c = getchar()) >= '0' && c <= '9') 18 Ans = Ans * 10 + c - '0' ; 19 return Ans * sign ; 20 } 21 22 void add(int a , int b){ 23 next[++ k] = head[a] , head[a] = k , to[k] = b ; 24 } 25 26 void DP(int a){ 27 f[a][0] = 0 ; 28 for(int i = head[a] ; i ; i = next[i]){ 29 int To = to[i] ; 30 DP(To) ; 31 for(int i = m ; i >= 0 ; -- i){ 32 for(int j = i ; j >= 0 ; -- j){ 33 f[a][i] = max(f[a][i] , f[a][j] + f[To][i - j]) ; 34 } 35 } 36 } 37 if(a){ 38 for(int i = m ; i >= 1 ; -- i){ 39 f[a][i] = f[a][i - 1] + value[a] ; 40 } 41 } 42 } 43 44 int main(){ 45 n = read() , m = read() ; 46 for(int i = 1 ; i <= n ; ++ i){ 47 a = read() , b = read() ; 48 add(a , i) ; 49 value[i] = b ; 50 } 51 DP(0) ; 52 cout << f[0][m] ; 53 return 0 ; 54 }