[CTSC1997]选课

柔情只为你懂 2021-10-23 14:36 263阅读 0赞

### [题面][Link 1] ###

### 题解 ###

树形背包板子题。

设\\(f\[i\]\[j\]\\)表示在以\\(x\\)为根的子树选\\(j\\)门课（包括\\(x\\)）能够获得的最高学分，用分组背包转移即可。

### 代码 ###

#include<cstdio> #include<vector> #define RG register inline int read() { int data = 0, w = 1; char ch = getchar(); while(ch != '-' && (ch < '0' || ch > '9')) ch = getchar(); if(ch == '-') w = -1, ch = getchar(); while(ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar(); return data*w; } const int maxn(310); std::vector<int> g[maxn]; typedef std::vector<int>::iterator iter; int s[maxn], f[maxn][maxn], n, m; void dfs(int x) { f[x][0] = 0; for(RG iter it = g[x].begin(); it != g[x].end(); ++it) { int to = *it; dfs(to); for(RG int v = m + 1; v; --v) for(RG int j = 0; j < v; ++j) f[x][v] = std::max(f[x][v], f[x][v - j] + f[to][j]); } } int main() { n = read(); m = read(); for(RG int i = 1; i <= n; i++) g[read()].push_back(i), f[i][1] = s[i] = read(); dfs(0); printf("%d\n", f[0][m + 1]); return 0; }

转载于:https://www.cnblogs.com/cj-xxz/p/9817568.html

[Link 1]: https://www.luogu.org/problemnew/show/P2014

发表评论取消回复

表情：

评论列表（有 0 条评论，263人围观）

还没有评论，来说两句吧...

相关阅读

相关 CMU ECE选课

15121基本数据结构，你要本科修过就不必听了，最深到二叉树堆排序。 15213好课，必选【请第一时间抢课，我的周花费20h】 15410好课，慎选【理由同son

青旅半醒/ 2022年05月13日 00:08/ 0 赞/ 157 阅读

相关选课

[选课][Link 1] 有n门课程，第i门课程的学分为\\(a\_i\\)，每门课程最多有一个先修课程，表示只有选了这一门课程才能选另一门课程，现在要从中选出m个课程，求最

ゝ一世哀愁。/ 2022年01月08日 00:27/ 0 赞/ 245 阅读

相关【Luogu 2014】选课

【题目链接】[传送门][Link 1] 【调试出错】写了第一遍怎么调都不过，气得想摔键盘。冷静去上了两节文化课回来又码了一遍，然后就一遍过了。【题解大意

淡淡的烟草味﹌/ 2022年01月07日 15:21/ 0 赞/ 256 阅读

相关 [Ctsc2015]misc

[https://lydsy.com/JudgeOnline/problem.php?id=4055][https_lydsy.com_JudgeOnline_problem.

蔚落/ 2022年01月06日 15:59/ 0 赞/ 210 阅读

相关 [CTSC2017]网络

[\[CTSC2017\]网络][CTSC2017] 连一条长度为len的边，使得基环树的直径最小结论：一定连在某条直径两个点上（否则更靠近不劣）然后二分答案判定。

清疚/ 2021年12月23日 15:09/ 0 赞/ 136 阅读

相关【loj2263】【CTSC2017】游戏

题目小\\(R\\)和小\\(B\\)一共完了\\(n\\)局游戏，第一局小\\(R\\)获胜的概率为\\(p\_i\\)，没有平局，对于第$ i $局游戏： 1.

╰半橙微兮°/ 2021年12月23日 01:41/ 0 赞/ 185 阅读

相关 P4218 [CTSC2010]珠宝商

P4218 \[CTSC2010\]珠宝商 -------------------- 神题... 可以想到点分治，细节不写了。。。（学了个新姿势，sam可以在前面

「爱情、让人受尽委屈。」/ 2021年12月09日 00:39/ 0 赞/ 169 阅读

相关【题解】CTSC1999家园(网络流)

CTSC1999家园建模方法类似我NOI2019网络同步赛我的T1写法\[【题解】[NOI2019Route\]（70分）][NOI2019Route_70] 问题的

ゝ一世哀愁。/ 2021年11月18日 01:20/ 0 赞/ 207 阅读

相关 [CTSC1997]选课

[题面][Link 1] 题解树形背包板子题。设\\(f\[i\]\[j\]\\)表示在以\\(x\\)为根的子树选\\(j\\)门课（包括\\(x\\)）能

柔情只为你懂/ 2021年10月23日 14:36/ 0 赞/ 264 阅读

相关 [CTSC2010]星际旅行

[https://www.luogu.org/problemnew/show/P4189][https_www.luogu.org_problemnew_show_P4189]

系统管理员/ 2021年09月29日 21:52/ 0 赞/ 232 阅读