小码匠的编程江湖【第77式】：树形DP入门题：选课

小码匠

发布于 2023-08-31 18:27:58

2220

发布于 2023-08-31 18:27:58

文章被收录于专栏：小码匠和老码农

对话

今天小码匠学习树形DP，按惯例要盘查她。

树形DP还是有些难度，的确要好好研究下，A掉选课，还有舞会。

开舞会何必请领导啊，自己玩多嗨啊。

哪都少不了匠她娘，很八卦，总是时不时出来捣乱。

目标驱动，打打鸡血，其实鸡血打多了往往就不管用了，但也习惯了。匠她娘还是挺会配合的，点个赞。

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 N 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 M 门课程学习，问他能获得的最大学分是多少？

输入格式

第一行有两个整数 N , M 用空格隔开。(1≤N≤300 , 1≤M≤300 )

接下来的 N 行,第 I+1 行包含两个整数和表示第I门课的直接先修课，表示第I门课的学分。若 =0 表示没有直接先修课（）。

输出格式

只有一行，选 M 门课程的最大得分。

输入输出样例

输入 #1复制

输出 #1复制

题目

题目原文请移步下面的链接

https://www.luogu.com.cn/problem/P2014
- 参考题解：https://www.luogu.com.cn/problem/solution/P2014
标签：OI、动态规划、树形DP

正解

树形dp+背包
因为每门课最多有一个先修课，所以可以考虑建树作dp，因为有些课是没有先修课程的，那么数据不就变成森林了吗，所以为了解决这个问题，我们建立一个学分为0的课程（编号为0）作为所有无先修课课程的先修课，这样我们就将森林变成了一棵以0号课程为根的树。
表示以u号点为根的子树中，已经遍历了u号点的前i棵子树，选了j门课程的最大学分。
转移的时候枚举u点的每个子结点v，同时枚举以为v根的子树选了几门课程，将子树的结果合并到根结点u上。
记点u的儿子个数为，以u为根的子树大小为siz，同时用滚动数组优化掉第二维，即表示节点u，选了j门课的最大学分）可以得到状态转移方程：

dp_{u, i+j} = max(dp_{u, i + 1} , dp_{u, i} + dp_{v, j})

代码

// 题目: [CTSC1997] 选课
// 链接: https://www.luogu.com.cn/problem/P2014
// 难度: 普及+/提高
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <array>
using namespace std;

int dp[305][305], s[305], n, m;


int dfs(int u, vector<vector<int>> &g) {
    int p = 1;
    dp[u][1] = s[u];
    for (auto v : g[u]) {
        int cnt = dfs(v, g);
        for (int i = min(p, m + 1); i > 0; --i){
            for (int j = 1; j <= cnt && i + j <= m + 1; ++j) {
                dp[u][i + j] = max(dp[u][i + j], dp[u][i] + dp[v][j]);
            }
        }
        p += cnt;
    }
    return p;
}

void best_coder() {
    scanf("%d%d", &n, &m);
    vector<vector<int>> g(n + 1);
    for (int i = 1; i <= n; i++) {
        int k;
        scanf("%d%d", &k, &s[i]);
        g[k].push_back(i);
    }
    dfs(0, g);
    printf("%d", dp[0][m + 1]);
}

void happy_coder() {

}

int main() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2023-08-11，如有侵权请联系 cloudcommunity@tencent.com 删除