首页/新闻资讯/正文详情

【题解-洛谷】P2014 [CTSC1997] 选课

发布时间:2026/9/26 2:36:17 来源:云帆数科 栏目:资讯中心
【题解-洛谷】P2014 [CTSC1997] 选课
题目P2014 [CTSC1997] 选课题目描述在大学里每个学生为了达到一定的学分必须从很多课程里选择一些课程来学习在课程里有些课程必须在某些课程之前学习如高等数学总是在其它课程之前学习。现在有N NN门功课每门课有若干学分分别记作s 1 , s 2 , ⋯ , s N s_1,s_2,\cdots,s_Ns1​,s2​,⋯,sN​每门课有一门或没有直接先修课若课程a aa是课程b bb的先修课即只有学完了课程a aa才能学习课程b bb。一个学生要从这些课程里选择M MM门课程学习问他能获得的最大学分是多少题目保证课程安排无冲突。即不会有a aa是b bb的先修课b bb也是a aa的先修课这类情况存在。输入格式第一行有两个整数N NNM MM用空格隔开( 1 ≤ N ≤ 300 (1 \leq N \leq 300(1≤N≤300,1 ≤ M ≤ 300 ) 1 \leq M \leq 300)1≤M≤300)。接下来的N NN行第i 1 i1i1行包含两个整数k i k_iki​和s i s_isi​k i k_iki​表示第i ii门课的直接先修课s i s_isi​表示第i ii门课的学分。若k i 0 k_i0ki​0表示没有直接先修课( 0 ≤ k i ≤ N (0 \leq {k_i} \leq N(0≤ki​≤N,1 ≤ s i ≤ 20 ) 1 \leq {s_i} \leq 20)1≤si​≤20)。数据保证至少存在一个k i 0 k_i0ki​0即至少一门课无先修课。输出格式只有一行选M MM门课程的最大学分。输入输出样例 #1输入 #17 4 2 2 0 1 0 4 2 1 7 1 7 6 2 2输出 #113思路代码#includebits/stdc.husingnamespacestd;constintN30010;intn,m,f[N][N],w[N];vectorintg[N];voiddfs(intu){f[u][0]0;//不选for(inti0;ig[u].size();i){//选intvg[u][i];dfs(v);for(intjm;j0;j--)//逆序枚举以u为根的子树选的课程数for(intk0;kj;k)//枚举u的子树选的课程数f[u][j]max(f[u][j],f[u][j-k]f[v][k]);}if(u){//加上选择u的学分for(intjm;j0;j--)f[u][j]f[u][j-1]w[u];}}intmain(){cinnm;for(inti1;in;i){intx,y;cinxw[i];g[x].push_back(i);//森林转化为树}dfs(0);coutf[0][m];return0;}结果

相关推荐

群晖NAS第三方硬盘兼容解锁:3步把硬盘写进兼容数据库
群晖NAS第三方硬盘兼容解锁:3步把硬盘写进兼容数据库

群晖NAS第三方硬盘兼容解锁:3步把硬盘写进兼容数据库 【免费下载链接】Synology_HDD_db Add your HDD, SSD and NVMe drives to your Synologys compatible drive database and a lot more 项目地址: https://gitcode.com/GitHub_Trending/sy/Synology_HDD_db … · 2026/9/26 2:36:11

数据库课程设计实战:员工考勤管理系统从需求到SQL实现
数据库课程设计实战:员工考勤管理系统从需求到SQL实现

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 2:36:11

gsd-core Worktree Prune 回归测试路径规范化:基于 `git worktree list --porcelain` 的跨平台断言方案
gsd-core Worktree Prune 回归测试路径规范化:基于 `git worktree list --porcelain` 的跨平台断言方案

【免费下载链接】gsd-core Git. Ship. Done - Core 项目地址: https://gitcode.com/gh_mirrors/ge/gsd-core 点击查看 免费下载 本文围绕 gsd-core 归档变更片段 fix-3056-worktree-path-assertion.md 展开:它记录了 PR #3117 对 worktree prune 回归测… · 2026/9/26 2:36:11

【Claude】SSL certificate verification 错误排查:NODE_EXTRA_CA_CERTS 自定义 CA 配置与 TaoToken 接入验证
【Claude】SSL certificate verification 错误排查:NODE_EXTRA_CA_CERTS 自定义 CA 配置与 TaoToken 接入验证

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 3:15:37

DeepSeek V4-Flash/Pro 实测报告:从购买到实战,TaoToken 统一 API 通道配置与验证
DeepSeek V4-Flash/Pro 实测报告:从购买到实战,TaoToken 统一 API 通道配置与验证

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 3:15:37

Cursor 配 TaoToken:AI 编程新纪元的 settings.json 配置骨架
Cursor 配 TaoToken:AI 编程新纪元的 settings.json 配置骨架

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 3:15:37

Vue 打包后 index.html 报 Refused to apply style?用 TaoToken 统一 Key 排查 LiveServer 与 dist 路径
Vue 打包后 index.html 报 Refused to apply style?用 TaoToken 统一 Key 排查 LiveServer 与 dist 路径

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 3:15:37

很牛X的右键菜单:用 TaoToken 统一 Key 打通 Cline 与 CC Switch 配置
很牛X的右键菜单:用 TaoToken 统一 Key 打通 Cline 与 CC Switch 配置

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 3:15:37

Tesseract中文OCR安装包配置与中国语识别实战
Tesseract中文OCR安装包配置与中国语识别实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 3:15:31

数据库课后习题答案别硬背:当测试用例集刷,效率翻倍
数据库课后习题答案别硬背:当测试用例集刷,效率翻倍

简介:万常选版《数据库原理与设计》课后习题答案资源,覆盖第2至6章及第9章,适合正在学习关系模型、数据库建模、关系数据理论与模式求精的本科生、自学者作为复习与自测材料。压缩包共7个文件,含3个doc参考答案、2个sql示例脚本、… · 2026/9/26 0:00:21

OpenClaw 替代品?Hermes Agent 踩坑实录:macOS 飞书接入 TaoToken 配置
OpenClaw 替代品?Hermes Agent 踩坑实录:macOS 飞书接入 TaoToken 配置

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/9/26 0:00:40

向下兼容与向上兼容:接口设计中的兼容性策略与工程实践
向下兼容与向上兼容:接口设计中的兼容性策略与工程实践

一次版本升级事故,是很多团队绕不过去的坎。线上环境里,服务端明明已经上线了新版接口,老的移动端还在照着旧文档传参数。请求一到网关,校验直接拒绝,用户操作失败,客服群炸了锅,开发群里开始互… · 2026/9/26 0:00:46

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码