P2014 [CTSC1997] 选课
题目描述
在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有NNN门功课，每门课有若干学分，分别记作s1,s2,⋯ ,sNs_1,s_2,\cdots,s_Ns1,s2,⋯,sN，每门课有一门或没有直接先修课（若课程aaa是课程bbb的先修课即只有学完了课程aaa，才能学习课程bbb）。一个学生要从这些课程里选择MMM门课程学习，问他能获得的最大学分是多少？
题目保证课程安排无冲突。（即不会有aaa是bbb的先修课，bbb也是aaa的先修课这类情况存在。）
输入格式
第一行有两个整数NNN，MMM用空格隔开(1≤N≤300(1 \leq N \leq 300(1≤N≤300,1≤M≤300)1 \leq M \leq 300)1≤M≤300)。
接下来的NNN行，第i+1i+1i+1行包含两个整数kik_iki和sis_isi，kik_iki表示第iii门课的直接先修课，sis_isi表示第iii门课的学分。若ki=0k_i=0ki=0表示没有直接先修课(0≤ki≤N(0 \leq {k_i} \leq N(0≤ki≤N,1≤si≤20)1 \leq {s_i} \leq 20)1≤si≤20)。
数据保证至少存在一个ki=0k_i=0ki=0，即至少一门课无先修课。
输出格式
只有一行，选MMM门课程的最大学分。
输入输出样例 #1
输入 #1
7 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2输出 #1
13C++实现
#include<iostream>#include<cstdio>#definemaxn1000usingnamespacestd;intn,m,f[maxn][maxn],head[maxn],cnt;structedge{intto,pre;}e[maxn];inlineintin(){chara=getchar();while(a<'0'||a>'9'){a=getchar();}intt=0;while(a>='0'&&a<='9'){t=(t<<1)+(t<<3)+a-'0';a=getchar();}returnt;}voidadd(intfrom,intto){e[++cnt].pre=head[from];e[cnt].to=to;head[from]=cnt;}voiddp(intnow){// f[now][0]=0;for(inti=head[now];i;i=e[i].pre){intgo=e[i].to;dp(go);for(intj=m+1;j>=1;j--){for(intk=0;k<j;k++){f[now][j]=max(f[now][j],f[go][k]+f[now][j-k]);}}}}intmain(){n=in(),m=in();for(inti=1;i<=n;i++){intfa=in();f[i][1]=in();add(fa,i);}dp(0);printf("%d\n",f[0][m+1]);return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
