CSTC 选课
2024-08-30 00:16:45
选课
[问题描述]
在大学里每个学生,为了达到一定的学分,必须从很多课程里选择一些课程来学习,在课程里有些课程必须在某些课程之前学习,如高等数学总是在其它课程之前学习。现在有N门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程a是课程b的先修课即只有学完了课程a,才能学习课程b)。一个学生要从这些课程里选择M门课程学习,问他能获得的最大学分是多少?
[输入]
第一行有两个整数N,M用空格隔开。(1<=N<=200,1<=M<=150) 接下来的N行,第I+1行包含两个整数ki和si, ki表示第I门课的直接先修课,si表示第I门课的学分。若ki=0表示没有直接先修课(1<=ki<=N, 1<=si<=20)。
[输出]只有一行,选M门课程的最大得分。:
样例输入:
7 4
2 2
0 1
0 4
2 1
7 1
7 6
2 2
样例输出:
13
树形DP,和前一篇POJ 2486有点相似。感觉树形DP的题都是讨论树与子树的问题。开始时竟因为先后关系用拓扑来想,后来发现,背包才是正解。又因为根是必选的,所以,在DP时应必须把根选上。
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int MAX=;
int st[MAX][MAX];
int val[MAX]; int tmp[MAX];
int n,m;
vector<int >G[MAX]; void dfs(int u){
int size=G[u].size(); int v;
for(int i=;i<size;i++){
v=G[u][i];
dfs(v);
for(int p=;p<=m;p++){
tmp[p]=st[u][p];
for(int k=;k<=p;k++){
if(p-k->=)
tmp[p]=max(tmp[p],st[u][p-k-]+st[v][k]+val[v]); //此处-1是因为根节点也算1
}
}
for(int j=;j<=n;j++)
st[u][j]=tmp[j];
}
} int main(){
int p,v;
while(scanf("%d%d",&n,&m)!=EOF){
val[]=;
memset(st,,sizeof(st));
for(int i=;i<=n;i++){
scanf("%d%d",&p,&v);
G[p].push_back(i);
val[i]=v; }
dfs();
int ans=st[][m]+val[];
printf("%d\n",ans);
}
return ;
}
最新文章
- Django入门实践(3)
- jQuery幸运大转盘_jQuery+PHP抽奖程序的简单实现
- Css学习笔记 (一)
- JDBC和JPA调用储存过程 接收存储过程有返回值
- AngularJS(11)-API
- Servlet课程0426(十一)Servlet Cookie实现两周内不用重复登录
- 大龄剩女四大结局:孤寡 后妈 拉拉 出家 宽带山KDS-宽带山社区-第一城市消费门户
- 区间dp-hdu-4745-Two Rabbits
- Android中TextView中内容不换行的解决方法
- window 远程在Linux(centOS7.0)上安装JDK以及配置环境变量
- 关于a标签颜色的探索
- Python的变量和常量
- JVM学习六:JVM之类加载器之双亲委派机制
- LeetCode 12. Integer to RomanLeetCode
- mac下shell给文件名批量加前缀
- log4j UdpAppender
- Chrome 开发工具之Timeline/Performance
- 【转】IntelliJ IDEA关联SVN
- sql将一张表的字段赋值给另一张表
- python-创建进程的三种方式
热门文章
- 洛谷P2593 [ ZJOI 2006 ] 超级麻将 —— DP
- Java中继承,类的高级概念的知识点
- HQL分页查询
- hdu 3037Saving Beans(卢卡斯定理)
- bzoj2287【POJ Challenge】消失之物(退背包)
- Appium + python - online-install-apk
- Spark2.0.2+Zeppelin0.6.2 环境搭建 初探
- ROS-URDF-Xacro
- B - IQ test
- intellij 创建java web项目(maven管理的SSH)