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

蔚落 2022-03-09 15:04 254阅读 0赞

**目录**

前言

题目

题目描述

输入输出格式

输入输出样例

解析

树形DP

建树

优化

转移

参考代码

--------------------

# 前言 #

已经好久时间没有更博了。。。

其实这段时间我可没有玩，而是在很努力地继续学习来着。。。

最近突然很沉迷于树形DP来着，于是乎呢，解决出了这道**“选课”**就来跟大家探讨一下。

这道题其实是树形dp的一道经典题目，而且其中并没有许多很难思考的关系，因此可以说是初学树形dp的人们（比方说我这种蒟蒻。。。）必做的一道题啦。

学会这道题以后，我相信其他类似这种的较为基础的题也不会难倒大家了。

# 题目 #

## 题目描述 ##

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

## 输入输出格式 ##

**输入格式：**

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

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

**输出格式：**

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

## 输入输出样例 ##

**输入样例\#1：**

7  4
    2  2
    0  1
    0  4
    2  1
    7  1
    7  6
    2  2

**输出样例\#1：**

# 解析 #

看到这道题，不知道大家有没有像我***这种的习惯性脑壳疼***，不管看到什么题都十分***烦躁***  。。。

不过我们再来好好看下，这道题似乎和  [金明的预算方案][Link 1]  有一点像，附件就相当于这里的先修课。**But**，大家如果再好好想想呢？或者说结合一下样例来分析分析。

**这里的先修课也许还会有先修课**。**并且一些课程的先修课相同。**

那么想到这里，我们就能够知道一件浅显易懂的事情了：**简单的线性DP已经不能满足这道题了。**

因此，我们就将引出—— **树形DP**。

## 树形DP ##

其实，树形DP并不像我们想象中的那么难，他就相当于一个**在树上进行的DP**罢了，意思也就是说，只是将背景**从线性换成了树**而已。因此，我们大可不必害怕，只需要像以前那样解DP就行了。

那么该怎么实现树形dp呢？其实最简单的方法，就是**通过DFS来实现基础树形DP**。

接下来，我们就来思考怎么建出这个树。

## 建树 ##

就依照样例来说吧，或许大家第一时间想到的，就是将先修课作为它的儿子连起来：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70][]

看了这个图，是不是感觉有点怪怪的样子？？

我们暂且先不管3这个节点吧，光看这个箭头是不是就不太对？一个节点怎么能有两个父亲呢？？这完全有悖常理吧。。。

因此，我们可以把箭头调转一个方向——

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 1][]

嗯嗯嗯，这样看起来就顺眼多了嘛。

不过，为什么要这样建树呢？？其实是可以说出理由的。

> 大家可以看到，一个有先修课的课程，必须要经过它的先修课后，才能够学习。
> 
> 这个也可以看做是一棵树，必须在通过这个节点的父节点后才能到达子节点。
> 
> 而且在这种情况下，就能够避免了类似上面的图的一个错误——一个节点或许有多个父亲。

### 优化 ###

可以看到上面一个图，其实是组成了一个森林，那么dfs的时候也就会再多一重循环来枚举每棵树的根节点，这也正是小题大做了。

因此，我们可以再**假想出一个根节点将这些树都连接起来，把森林变成一棵树**。

而这个根节点的不二人选，自然也就是 **0号节点** 啦。

而且我们也可以从样例中看出来 （***不用再往前翻了，我这里贴出来***）——

7  4
    2  2
    0  1
    0  4
    2  1
    7  1
    7  6
    2  2

先修课的先修课自然就是0号节点，那么我们可以直接通过样例建树了。

也就不用再花时间自己再来重新建一遍（***我就最讨厌这样了***）。

最后的形状如图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 2][]

## 转移 ##

既然已经思考完了建树，那么我们就该考虑考虑重头戏了——**dp的转移**。

按照平时的惯例，**第一维肯定是状态变量**，但是因为还有选的课程数的限制，因此，我们还得**多加一维来存储已经选了多少门课程**。

所以就有 ![\{\\color\{Red\} dp\_\{i, j\}\}][color_Red_ dp_i_ j] 表示为**以i为根的子树选了j门课程的学分的最大值**。

那么这个dp到底该如何转移呢？

我们可以再设一个变量k，表示为i节点的一个儿子选了k门课程，那么它的剩余的儿子们就只能选j - k - 1门课程了。

可是为什么要减1呢？其实很简单，因为**还要加上i这门课程**啊，如果他不选的话，那么他的儿子们就一个也选不到了。

至此，我们就推出了转移公式：

**![\{\\color\{Red\} dp\_\{i, j\} = max\\left \\\{ dp\_\{sonv, k\} + dp\_\{i, j - k \_ 1\} + w\[i\] \\right \\\}\}][color_Red_ dp_i_ j_ _ max_left _ dp_sonv_ k_ _ dp_i_ j - k _ 1_ _ w_i_ _right]**

w\[i\]就是第i门课程的学分。

# 参考代码 #

#include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <algorithm>
    #include <cstring>
    #include <vector>
    using namespace std;
    #define min(a, b) a < b ? a : b
    #define max(a, b) a > b ? a : b
     
    void read (int &x){
        int f = 1; x = 0;
        char c = getchar ();
        while (c < '0' || c > '9'){
            if (c == '-') f = -1;
            c = getchar ();
        }
        while (c >= '0' && c <= '9'){
            x = (x << 1) + (x << 3) + c - 48;
            c = getchar ();
        }
        x *= f;
    }
     
    void print (int x){
        if (x < 0){
            putchar ('-');
            x = ~(x) + 1;
        }
        if (x / 10) print (x / 10);
        putchar (x % 10 + 48);
    }
     
    #define N 300
     
    struct edge{
        int v, w;
        edge (){};
        edge (int V, int W){
            v = V; w = W;
        }
    };
    int n, m, dp[N + 5][N + 5], sz[N + 5];
    vector <edge> G[N + 5];
     
    void dfs (int u, int f){
        for (int i = 0; i < G[u].size (); i++){
            int v = G[u][i].v;
            if (v == f) continue;
            dfs (v, u);
            sz[u] += sz[v] + 1;
            for (int j = min (sz[u], m); j; j--){
                for (int k = 0; k < j && k <= sz[v]; k++){
                    dp[u][j] = max (dp[u][j], dp[v][k] + dp[u][j - k - 1] + G[u][i].w);
                }
            }
        }
    }
     
    int main (){
        read (n); read (m);
        for (int i = 1; i <= n; i++){
            int u, w;
            read (u); read (w);
            G[u].push_back (edge (i, w));
        }
        dfs (0, -1);
        print (dp[0][m]);
    }

[Link 1]: https://www.luogu.org/problemnew/show/P1064
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70]: /images/20220309/fa6d5e2a666c4218b9fa17775bc091d8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 1]: /images/20220309/276dbbcd55204d3ba6d50ff6bdaa406b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzkyNTIzOQ_size_16_color_FFFFFF_t_70 2]: /images/20220309/10c197240993459bad3c20d9b1307c10.png
[color_Red_ dp_i_ j]: https://private.codecogs.com/gif.latex?%7B%5Ccolor%7BRed%7D%20dp_%7Bi%2C%20j%7D%7D
[color_Red_ dp_i_ j_ _ max_left _ dp_sonv_ k_ _ dp_i_ j - k _ 1_ _ w_i_ _right]: https://private.codecogs.com/gif.latex?%5Cfn_jvn%20%7B%5Ccolor%7BRed%7D%20dp_%7Bi%2C%20j%7D%20%3D%20max%5Cleft%20%5C%7B%20dp_%7Bsonv%2C%20k%7D%20&plus;%20dp_%7Bi%2C%20j%20-%20k%20_%201%7D%20&plus;%20w%5Bi%5D%20%5Cright%20%5C%7D%7D