洛谷P2014《选课》

五月 11, 2019 2239

森林上的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
2
3
4
5
6
7
8
7  4
2  2
0  1
0  4
2  1
7  1
7  6
2  2

输出样例

1
13

解题思路

注意到题目中的「每门课有一门或没有直接先修课」
所以这是一个森林

我们用一个虚拟点0把所有的树根连起来，构成一棵大树
接下来这个题目就从一个DAG上DP转化为了一个树形DP
但是！它事一个树形背包

设dp[i][j]表示选以i为根的树j个节点

初始化方程：
dp[child][i] = dp[root][i] + weight[root]
(0 <= i < 还能选择的节点数)
至于为什么从零开始……因为可以选择的节点是root的子树的节点数减一，毕竟root占掉了一个节点

转移方程：
dp[root][i] = std::max(dp[root][k], dp[child][k-1]);
(1 <= i <= 还能选择的节点数)

答案：
dp[0][m]

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// luogu-judger-enable-o2
#include <iostream>
#include <vector>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

const int MAXN = 300 + 10;

int dp[MAXN][MAXN];

/*
 *
 * 首先这是一个森林
 * 令 f[i][j] 表示以 i 为根的子树选择前 j 个点的最大价值
 *
 */

struct Graph {
    std::vector<int> head[MAXN];
    int weight[MAXN];
    
    void addEdge(int prev, int next, int w) {
        head[prev].push_back(next);
        weight[next] = w;
    }
    void DFS(int root, int k) {
        if (k == 0) return; // 没得选了
        for (auto now : head[root]) {
            for (int i = 0; i < k; ++i) {
                dp[now][i] = dp[root][i] + weight[now];
            }
            DFS(now, k - 1); // 对子树进行选择
            for (int i = 1; i <= k; ++i) {
                dp[root][i] = std::max(dp[root][i], dp[now][i-1]);
            }
        }
    }
} G;

int main() {
    IMPROVE_IO();
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        int prev, weight;
        cin >> prev >> weight;
        G.addEdge(prev, i, weight);
    }
    G.DFS(0, m);
    cout << dp[0][m] << endl;
    return 0;
}