【Luogu 2014】选课

淡淡的烟草味﹌ 2022-01-07 15:21 306阅读 0赞

### 【题目链接】[传送门][Link 1] ###

### 【调试出错】 ###

写了第一遍怎么调都不过，气得想摔键盘。

冷静去上了两节文化课回来又码了一遍，然后就一遍过了。

### 【题解大意】 ###

这个题目给的是森林，我们构建虚拟节点0使之变成一棵树。

f\[x,t\]表示以x为根的子树中选择t门课程能获得的最高学分。设x的子节点集合为son\[x\]。

### 【code】 ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include<bits/stdc++.h>
    using namespace std;
    const int N = 306;
    vector<int> son[N];
    int n, m, f[N][N], s[N];
    
    void dp(int x) {
        f[x][0] = 0;
        for (unsigned int i = 0; i < son[x].size(); i++) {
            int y = son[x][i];
            dp(y);
            for (int t = m; t >= 0; t--)
                for (int j = t; j >= 0; j--)
                    if (t - j >= 0)
                        f[x][t] = max(f[x][t], f[x][t-j] + f[y][j]);
        }
        if (x) for(int t = m; t; t--) f[x][t] = f[x][t-1] + s[x];
    }
    
    int main() {
        cin >> n >> m;
        for (int i = 1; i <= n; i++) {
            int x;
            cin >> x >> s[i];
            son[x].push_back(i);
        }
        memset(f, 0xcf, sizeof(f));
        dp(0);
        cout << f[0][m] << endl;
        return 0;
    }

### 【题目链接】传送门 ###

### 【题解大意】 ###

输出方案！

一般dp怎么输出方案呢。

用与dp状态大小相同的数组记录出当前的最优值是由什么转移而来的，通过一次递归沿着记录的状态来源回到最初状态。

### 【code】 ###

转载于:https://www.cnblogs.com/ve-2021/p/10813568.html

[Link 1]: https://www.luogu.org/problemnew/show/P2014
[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211220/184f52920fcc4585aa5ffec4d65f0a2e.png

发表评论取消回复

表情：

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

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

相关阅读

相关 P2014 选课

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

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

相关选课大作战

选课大作战 Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^\_^ 题目描述眼看着大一新生就要来了，原大一的

小鱼儿/ 2022年08月18日 02:30/ 0 赞/ 185 阅读

相关 CMU ECE选课

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

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

相关选课（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 赞/ 307 阅读

相关 Luogu P3577 [POI2014]TUR-Tourism

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

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

相关 Luogu2375 [NOI2014]动物园（KMP）

写炸，上网，不同KMP形态。无力，照该，一换写法就过。横批：我是垃圾求\\(next\\)时\\(DP\\)出\\(num\\)，路径压缩防卡\\(n^2

系统管理员/ 2021年11月17日 05:12/ 0 赞/ 339 阅读

相关 luogu P2014 选课（树形dp）

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

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

相关 [CTSC1997]选课

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

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