Acwing-286-选课(树上DP)
2024-09-05 08:44:29
链接:
https://www.acwing.com/problem/content/288/
题意:
学校实行学分制。
每门的必修课都有固定的学分,同时还必须获得相应的选修课程学分。
学校开设了 N 门的选修课程,每个学生可选课程的数量 M 是给定的。
学生选修了这 M 门课并考核通过就能获得相应的学分。
在选修课程中,有些课程可以直接选修,有些课程需要一定的基础知识,必须在选了其他的一些课程的基础上才能选修。
例如《Windows程序设计》必须在选修了《Windows操作基础》之后才能选修。
我们称《Windows操作基础》是《Windows程序设计》的先修课。
每门课的直接先修课最多只有一门。
两门课可能存在相同的先修课。
你的任务是为自己确定一个选课方案,使得你能得到的学分最多,并且必须满足先修条件。
假定课程之间不存在时间上的冲突。
思路:
Dp[x, j], 表示以x为根, 选j门课的最大学分, 对于有先修课的课, 从先修课连一条边, 没有的连到0.
跑Dfs, 从下往上dp.
代码:
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500;
vector<int> G[MAXN];
int val[MAXN];
int dp[MAXN][MAXN];
int n, m;
void Dfs(int u)
{
for (int i = 0;i < G[u].size();i++)
{
int node = G[u][i];
Dfs(node);
for (int j = m;j >= 0;j--)
{
for (int k = j;k >= 0;k--)
{
if (j-k >= 0)
dp[u][j] = max(dp[u][j], dp[u][j-k]+dp[node][k]);
}
}
}
if (u != 0)
{
for (int i = m;i >= 1;i--)
dp[u][i] = dp[u][i-1]+val[u];
}
}
int main()
{
scanf("%d%d", &n, &m);
int h, v;
for (int i = 1;i <= n;i++)
{
scanf("%d%d", &h, &v);
G[h].push_back(i);
val[i] = v;
}
Dfs(0);
printf("%d\n", dp[0][m]);
return 0;
}
最新文章
- LA
- [设计模式] javascript 之 策略模式
- [Reactive Programming] Async requests and responses in RxJS
- python 加密模块安装
- 华为-on练习--重复的字符过滤
- 【二十三】php之预定义超全局变量
- hdu 5893 (树链剖分+合并)
- [Oracle][RMAN]关于Oracle RMAN里面的Merged Incremental Backups的Tag分离机能
- 用clock()函数计时的坑
- 「PKUWC 2018」Minimax
- iis 发布mvc
- Selenium Grid的Java调用方法
- Linux __attribute__((";hidden";))、default
- 如何不使用Navigator空间实现跳转页面?
- Scala中的数组和集合操作
- Java不同场景oom错误探究及解决办法
- 解题:洛谷4721 [模板]分治FFT
- 构建一个完整的DNS系统
- zabbix报警优化
- Java之戳中痛点 - (5)switch语句break不能忘以及default不同位置的用法
热门文章
- Linux 下面安装 nginx 以及进行TCP反向代理、负载均衡的过程
- HanLP封装为web services服务的过程介绍
- jenkins持续集成(windows slave+svn+.net)
- IO多路复用技术详解
- java日志框架系列(3):logback框架配置详解
- 第7章:LeetCode--算法:递归问题
- REST架构中的HTTP动词
- global和nonlocal的区别
- k8s之dashboard认证、资源需求、资源限制及HeapSter
- Spring实战(三)Spring中装配Bean的三种方式---XML、JavaConfig、AutoWire