打卡信奥刷题（2526）用C++实现信奥 P2014 [CTSC1997] 选课

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

13

C++实现

#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考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容