当前位置：首页 > news >正文

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

news 2026/8/27 15:57:14

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

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