1 题意
题目:。
有 N 门课程,每门课有学分,且至多有一门直接先修课。选择一门课之前,必须选完它的所有先修课。要求恰好选择 M 门课,求最大学分总和。
原题中 N,M≤300,每门课的学分为 1∼20,依赖关系无环。
从先修课向后续课连边,得到一片有根森林。一个合法选择包含某门课程时,必须包含它到所在树根的所有祖先。这与 二叉苹果树 中“选择后代必须先接通祖先”的限制相同。
2 虚拟根
没有先修课的课程可能不止一门。新增节点 0,将所有没有先修课的课程接在它下面,森林就变为一棵树。
规定虚拟根的学分为 0,且最终方案必须包含它。真实课程恰好选 M 门,就对应树中包含虚拟根的 M+1 个节点。

图中虚线是新增关系,节点旁标学分。选择 1,4,5,满足依赖,真实课程数是 3;放入 DP 时再计入虚拟根,共 4 个节点。
3 状态定义
令 K=M+1。对于 j≥1,定义 f[u][j] 为:从 u 的子树中恰好选择 j 个节点,必须包含 u,并满足依赖关系时的最大学分。
另外规定 f[u][0]=0,表示整棵子树不选。初始化为:
f[u][0]=0,f[u][1]=su,其余状态为 −∞。这里 s0=0,所以虚拟根的初值为 f[0][1]=0。
不能把“恰好选择 j 门”写成“至多选择 j 门”,却仍使用同一套初值。状态数量不足与合法的零收益,是不同的情况。
4 合并孩子
沿用上一篇的逐个合并。设旧部分已经包含 u 和若干孩子子树,当前合并孩子 v:
next[a+b]=max(next[a+b],f[u][a]+f[v][b]).其中 a≥1、b≥0、a+b≤K。
- a≥1:旧部分已经选择 u。
- b=0:当前孩子子树完全不选。
- b>0:孩子子树方案已经包含 v,因此选择 v 所需的直接先修课 u 也在方案内。
每次合并使用独立的 next 数组,合并后再覆盖旧数组。孩子之间只通过 u 相连,逐个合并不会破坏依赖,也不会重复选择同一门课程。
这一问题按课程数量分配名额。更一般的“每件物品占用不同容量”的模型,见 有依赖的背包。
5 手算示例
图中的课程信息如下,先修课为 0 表示没有先修课:
| 课程 |
直接先修课 |
学分 |
| 1 |
0 |
2 |
| 2 |
1 |
8 |
| 3 |
1 |
5 |
| 4 |
0 |
6 |
| 5 |
4 |
9 |
以 1 为根的子树,选择 0,1,2,3 门课的最优值分别为 0,2,10,15;以 4 为根的子树,对应 0,1,2 门课的最优值为 0,6,15。
现在选 M=3 门真实课程。虚拟根先占一个节点名额,剩余三个分给两棵课程子树:
| 分给子树 1 |
分给子树 4 |
最大学分 |
| 0 |
3 |
不可行,子树 4 只有两门课 |
| 1 |
2 |
2+15=17 |
| 2 |
1 |
10+6=16 |
| 3 |
0 |
15+0=15 |
答案为 f[0][4]=17。如果错误地输出 f[0][3],就只选了两门真实课程。
示例输入输出
输入:
1
2
3
4
5
6
5 3
0 2
1 8
1 5
0 6
4 9
输出:
6 子树大小裁剪
合并前,令 A=sz[u] 为旧部分的节点数,B=sz[v] 为当前孩子子树的节点数。枚举范围限制为:
1≤a≤min(A,K),0≤b≤min(B,K−a).不能让旧部分选择超过 A 个节点,也不能让孩子子树提供超过 B 个节点。合并完成后,再令 sz[u]←A+B。
若每次都扫描完整的两个 K 范围,时间上界为 O(NK2)。使用上述范围后,可以证明总时间为 O(NK),其中 N=n+1,包含虚拟根。
先看一个较直观的 O(N2) 上界:忽略名额限制,一次合并的正数数量对 (a,b) 至多有 AB 个。把各个节点起初看作单点集合,按程序顺序合并;任意两个节点只会在其所属集合首次合并时跨集合配对一次,所以所有 AB 之和为 (2N)。
这给出的是枚举次数的上界。实际还有 a+b≤K、不可行状态跳过等限制,不能据此声称代码循环次数始终严格等于点对数。
更紧的 O(NK) 时间界
只考虑 b≥1,一次合并的枚举次数不超过 min(A,K)min(B,K)。定义:
Φ(s)={s2,2Ks−K2,s≤K,s>K.对任意正整数 A,B,有:
min(A,K)min(B,K)≤Φ(A+B)−Φ(A)−Φ(B).可以按是否超过 K 验证:两者之和不超过 K 时,右侧为 2AB;两者都至少为 K 时为 K2;一大一小时为 2KB−B2≥KB,其中 B≤K。最后一种情况是 A,B<K<A+B,右侧为 2AB−(A+B−K)2≥AB,因为 A+B−K≤min(A,B)。
从 N 个单点集合合并到整棵树,所有势能差相加,内部项抵消,总和为 Φ(N)−NΦ(1)≤2NK。
另外,b=0 的处理、数组初始化和复制,每个节点或每次孩子合并至多花 O(K),总计仍为 O(NK)。因此完整实现的时间复杂度为 O(NK)。
7 正确性
每个真实课程方案加入虚拟根后,都唯一对应一个包含根的合法树上方案,且节点数增加 1、学分不变。
一次合并中,任意合法方案在旧部分和当前孩子子树内的选择,分别对应枚举中的 a,b。若孩子子树非空,其根与先修课 u 都被选,依赖成立;反过来,任意两个合法子方案也都能这样合并。
按孩子数归纳,合并后保留了各个数量下的最大学分。故 f[0][M+1] 恰好是选择 M 门真实课程的最优值。
8 代码实现
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
#include <bits/stdc++.h>
using namespace std;
const int maxn = 300 + 5;
const int NEG = -1000000000;
vector<int> g[maxn];
int score[maxn], sz[maxn], f[maxn][maxn];
int n, m, K;
void dfs(int u) {
for (int j = 0; j <= K; ++j) f[u][j] = NEG;
f[u][0] = 0;
f[u][1] = score[u];
sz[u] = 1;
int next[maxn];
for (int v : g[u]) {
dfs(v);
fill(next, next + K + 1, NEG);
for (int a = 1; a <= min(sz[u], K); ++a) {
if (f[u][a] == NEG) continue;
for (int b = 0; b <= min(sz[v], K - a); ++b) {
if (f[v][b] == NEG) continue;
next[a + b] = max(next[a + b], f[u][a] + f[v][b]);
}
}
for (int j = 1; j <= K; ++j) f[u][j] = next[j];
sz[u] += sz[v];
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
K = m + 1;
for (int u = 1; u <= n; ++u) {
int parent;
cin >> parent >> score[u];
g[parent].push_back(u);
}
dfs(0);
cout << f[0][K] << '\n';
return 0;
}
时间复杂度为 O((n+1)(M+1)),空间复杂度相同。原题学分总和不超过 300×20,使用 int 即可。不可行状态先检查,再进行加法。
9 相关题解
暂无相关题解