信息学奥赛一本通 提高组 1576：选课

【题目描述】

原题来自：CTSC 1997

大学实行学分制。每门课程都有一定的学分，学生只要选修了这门课并通过考核就能获得相应学分。学生最后的学分是他选修各门课的学分总和。

每个学生都要选择规定数量的课程。有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其他的一些课程基础上才能选修。例如《数据结构》必须在选修了《高级语言程序设计》后才能选修。我们称《高级语言程序设计》是《数据结构》的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述，每门课都有一个课号，课号依次为 1,2,3,⋯$1,2,3,\cdots$。

下面举例说明：

上例中课号 1$1$ 是课号 2$2$ 的先修课，即如果要先修课号 2$2$，则课号 1$1$ 必定已被选过。同样，如果要选修课号 33 ，那么课号 1$1$ 和 课号 2$2$ 都一定被选修过。

学生不可能学完大学开设的所有课程，因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。请找出一种选课方案使得你能得到的学分最多，并满足先修课优先的原则。假定课程间不存在时间上的冲突。

【输入】

输入的第一行包括两个正整数 M,N$M,N$，分别表示待选课程数和可选课程数。

接下来 M$M$ 行每行描述一门课，课号依次为 1,2,⋯,M$1,2,\cdots ,M$。每行两个数，依次表示这门课先修课课号（若不存在，则该项值为 0$0$）和该门课的学分。

各相邻数值间以空格隔开。

【输出】

输出一行，表示实际所选课程学分之和。

【输入样例】

7 4
2 2
0 1
0 4
2 1
7 1
7 6 
2 2

【输出样例】

13

这个题用到两个知识点：

1. 森林转二叉树

2. 树上的dp,只需考虑左右孩子如何决定根节点状态。

   
   

设f[i][j]表示以i为选修课，选择j门课程的最大学分。

则  第一种情况：不选i，则选i的右孩子(兄弟节点)    f[node[i].right][j]

     第二种情况： 选择i,  则考虑做孩子k个，右孩子j-k-1个节点    f[node[i].left][k]+f[node[i].right][j-k-1]+node[i].score      0<k<j

#include <bits/stdc++.h>
using namespace std;
int bianhao,point;
struct Node{
	int l;
	int r;
	int score;
	};
Node node[10010];int f[10010][10010];
int leftc;
	
void init(int m,int n){
	int i;
	for(i=1;i<=m;i++){
		cin>>bianhao>>node[i].score;
		if(!node[bianhao].l){
			node[bianhao].l=i;
		//	=point;
		}
		else{
			leftc=node[bianhao].l;
			while(node[leftc].r){
				leftc=node[leftc].r;
			}
			node[leftc].r=i;
			//node[leftc].score=point;
		}
	}
	return ;
	}
	
int dfs(int m,int n){	
	if(f[m][n]>0){ 
		return f[m][n]; 
	} 
	if(m==0||n==0) return f[m][n]=0;
	
	int tmp1=dfs(node[m].r,n);
	for(int k=0;k<n;k++){
	 	int tmp2=dfs(node[m].l,k)+dfs(node[m].r,n-k-1)+node[m].score;	
		if(tmp1<tmp2){
			tmp1=tmp2;
		}
	}   
	return f[m][n]=tmp1;
	}
	
int main(){
	int m,n,i,j,k;
	cin>>m>>n;
	init(m,n);
	//cout<<node[5].l<<" "<<node[5].r<<endl;
	//dfs(m,n);
	memset(f,0,sizeof(f));
	int res=0;
	//for(int i=1;i<=m;i++) 
	  //cout<<node[i].score<<" ";
	//cout<<point[i]<<" ";
	cout<<dfs(node[0].l,n);
	return 0;
}