当前位置:首页 > NOIP > 正文

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

时间限制: 1000 ms         内存限制: 524288 KB
提交数: 135     通过数: 107 

【题目描述】

原题来自:CTSC 1997

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

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

下面举例说明:


课号先修课号学分
11
211
323
43
524


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

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

【输入】

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

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

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

【输出】

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

【输入样例】

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

【输出样例】

13

【提示】

数据范围与提示:

1NM100,学分不超过 20




这个题用到两个知识点:

  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;
}


更新时间 2019-06-25

有话要说...