P2014 选课

爱被打了一巴掌 2023-06-01 15:53 22阅读 0赞

### P2014 选课 ###

[题目链接][Link 1]

这道题目是一个比较简单的树形\\(DP\\),有限制的背包问题，转化为树上问题就是要选本节点必须选这棵子树的根节点，最大化价值。

首先，设`dp[i][j]`表示**枚举到**标号为\\(i\\)的子树中选了\\(j\\)个节点的最大价值。

预处理：`dp[i][1]=val[i]`，在枚举到\\(i\\)这棵子树中只选一个节点，所以只能选根节点。

因为用0节点作为虚根节点，使这个森林成为一棵树，所以可用的空间应该到\\(k+1\\)，默认根节点必须选。

转移： for (int j=m+1;j>=1;j--) { for (int k=0;k<j;k++) dp[x][j]=max(dp[x][j],dp[ed[i].e][k]+dp[x][j-k]); }

\\(k=0\\),表示不选这棵子树的所有节点及根节点

\\(k<j\\),因为k!=0时默认选根节点，所以可以选的节点数目是\\(k-1\\)。

一种是保持原来的状态，一种是在当前子树（除根节点外）选k个节点，取\\(\\max\\)。

因为初始化根节点必须选，所以不用特判。

说的我自己都信了。

// luogu-judger-enable-o2 #include<iostream> #include<cstdio> using namespace std; const int N=3e2+100; struct edge{ int s,e,net; }ed[N]; int n,m,tot; int dp[N][N]; int head[N]; inline void dfs(int x) { for (int i=head[x];i;i=ed[i].net) { dfs(ed[i].e); for (int j=m+1;j>=1;j--) { for (int k=0;k<j;k++) dp[x][j]=max(dp[x][j],dp[ed[i].e][k]+dp[x][j-k]); } } return ; } inline void add(int s,int e) { ed[++tot]=(edge){s,e,head[s]}; head[s]=tot; return ; } int main() { scanf("%d%d",&n,&m); for (int i=1;i<=n;i++) { int fa; scanf("%d%d",&fa,&dp[i][1]); add(fa,i); } dfs(0); printf("%d\n",dp[0][m+1]); return 0; }

转载于:https://www.cnblogs.com/last-diary/p/11402897.html

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

发表评论取消回复

表情：

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

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

相关阅读

相关洛谷P2387 [NOI2014]魔法森林(LCT)

魔法森林 [题目传送门][Link 1] 解题思路把每条路按照\\(a\\)的值从小到大排序。然后用LCT按照b的值维护最小生成树，将边按照顺序放入。如果\\(

一时失言乱红尘/ 2023年08月17日 17:21/ 0 赞/ 113 阅读

相关 P2014 选课

P2014 选课 [题目链接][Link 1] 这道题目是一个比较简单的树形\\(DP\\),有限制的背包问题，转化为树上问题就是要选本节点必须选这棵子树的根节点，最大

爱被打了一巴掌/ 2023年06月01日 15:53/ 0 赞/ 23 阅读

相关选课（LGOJ P2014）—— 树形DP基础

目录前言题目题目描述输入输出格式输入输出样例解析树形DP 建树优化转移参考代码 -------------------- 前言

蔚落/ 2022年03月09日 15:04/ 0 赞/ 229 阅读

相关选课

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

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

相关【Luogu 2014】选课

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

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

相关 Luogu P3577 [POI2014]TUR-Tourism

Luogu P3577 \[POI2014\]TUR-Tourism [题目链接][Link 1] 题目大意：给出一张\\(n\\)个点，\\(m\\)条边的无向图，保

浅浅的花香味﹌/ 2021年12月20日 10:23/ 0 赞/ 193 阅读

相关 luogu P2014 选课（树形dp）

[传送门][Link 1] 题意：现在有很多门课程，但是每门课程都会依赖某些其他的课程（即学了第\\(a\_i\\)门课程之后才能学习第\\(a\_\{i+1\}\\

女爷i/ 2021年11月05日 13:16/ 0 赞/ 389 阅读

相关 P2114 [NOI2014]起床困难综合症

题目描述 21世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。作为一名青春阳光好少年，atm一直坚持与起床困难综合症作斗争。通过研究相

╰半夏微凉°/ 2021年11月02日 01:00/ 0 赞/ 271 阅读

相关 P2375 [NOI2014]动物园(kmp)

考虑num数组与next数组的区别。 1. 如何统计数目。根据border那一套理论，s的所有border长度为 f a i l \[ n \] , f a i l \[

电玩女神/ 2021年09月07日 06:08/ 0 赞/ 323 阅读

相关 P3573 [POI2014]RAJ-Rally

很妙的思路首先这是一个DAG，于是我们先在原图和反图上各做一遍，分别求出\(diss_i\)和\(dist_i\)表示从\(i\)点出发的最短路和以\(i\)为终点的最...

小灰灰/ 2021年03月28日 15:42/ 0 赞/ 332 阅读