[Luogu-P2014] 选课

发表于 | 更新于 | 分类于 ， ，
本文字数： 12k

链接

\(\text{Luogu-P2014 选课}\)

题意

  这里有\(n\)个课程，你需要从它们中选出一些来学习，然而有些课程必须在某些课程之前学习，如高等数学总是在其他课程之前学习。每门课程有个学分，对于一门课必须先修它的先修课才能再修它，你需要从这些课程里选择m门课程学习，问它能获得的最大学分。

  输入格式：第一行两个整数\(n,m\)用空格隔开，接下来\(n\)行，第\(i+1\)包含两个整数\(k\)和\(s\)，\(k\)表示第\(i\)门课的直接先修课，\(s\)表示第\(i\)门课的学分，\(k=0\)表示没有直接先修课。

  数据范围：\(1\leq n\leq 300,1\leq m\leq 300,1\leq k\leq n,1\leq s\leq 20\).

  输出格式：输出一行，选\(m\)门课的最大得分。

分析

  这是一个树形背包的经典入门题。

  没门课的先修课最多只有一个，所以课与课之前的先修关系构成了一棵树。我们构造一个虚拟节点0，对于那些没有先修课的课程，规定先修课为0，并且选0的学分为0，那么问题就转化成了，从这个以0为根节点的树中，选\(m+1\)门课。

  设\(dp[x][t]\)表示在以\(x\)为根的子树中选取\(t\)门课，能获得的最大学分，对于\(x\)的每个子节点\(y_i\)，我们可以在以\(y_i\)为根的子树中选修若干门课\(c_i\)，在满足\(\sum c_i=t-1\)的基础上获得尽量多的学分。

  这即是一个分组背包，物品组数为\(x\)子节点\(y_i\)的个数，每组物品共\(t-1\)个，背包体积为\(t-1\)，第\(i\)组第\(j\)个物品体积为\(j\)。

代码

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
61
62
63
64
65
66
67
68
69
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <ostream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <unordered_map>
#include <vector>

#define INF 0x7f7f7f7f
#define MAXN 2000005
#define N 200005
#define P 2
//#define MOD 99991
#define MOD(a, b) a >= b ? a % b + b : a

typedef long long ll;

namespace fastIO {
    //#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin),
    // p1 == p2) ? EOF : *p1++) char buf[(1 << 22)], *p1 = buf, *p2 = buf;
    inline int read() {
        char c = getchar();
        int x = 0, f = 1;
        while (c < '0' || c > '9') {
            if (c == '-')
                f = -1;
            c = getchar();
        }
        while (c >= '0' && c <= '9')
            x = x * 10 + c - '0', c = getchar();
        return x * f;
    }
}  // namespace fastIO

using namespace fastIO;
using namespace std;

int n, m, k, f[305][305], s[305];

vector<int> vec[305];

void dfs(int u) {
    f[u][1] = s[u];
    for (int i = 0; i < vec[u].size(); i++) {
        int v = vec[u][i];
        dfs(v);
        for (int j = m + 1; j > 0; j--)
            for (int k = 0; k < j; k++)
                f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
    } 
}

int main() {
    //freopen("test.in", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> k >> s[i];
        vec[k].push_back(i);
    }
    dfs(0);
    cout << f[0][m + 1] << endl;
}