选课

1 题意

题目:luogu P2014: [CTSC1997] 选课。

有 NN 门课程,每门课有学分,且至多有一门直接先修课。选择一门课之前,必须选完它的所有先修课。要求恰好选择 MM 门课,求最大学分总和。

原题中 N,M≤300N,M\le300,每门课的学分为 1∼201\sim20,依赖关系无环。

从先修课向后续课连边,得到一片有根森林。一个合法选择包含某门课程时,必须包含它到所在树根的所有祖先。这与 二叉苹果树 中“选择后代必须先接通祖先”的限制相同。

2 虚拟根

没有先修课的课程可能不止一门。新增节点 00,将所有没有先修课的课程接在它下面,森林就变为一棵树。

规定虚拟根的学分为 00,且最终方案必须包含它。真实课程恰好选 MM 门,就对应树中包含虚拟根的 M+1M+1 个节点。

虚拟根 0 连接两棵课程树;1 的后续课为 2、3,4 的后续课为 5;选择真实课程 1、4、5,学分为 17

图中虚线是新增关系,节点旁标学分。选择 1,4,51,4,5,满足依赖,真实课程数是 33;放入 DP 时再计入虚拟根,共 44 个节点。

3 状态定义

令 K=M+1K=M+1。对于 j≥1j\ge1,定义 f[u][j]f[u][j] 为:从 uu 的子树中恰好选择 jj 个节点,必须包含 uu,并满足依赖关系时的最大学分。

另外规定 f[u][0]=0f[u][0]=0,表示整棵子树不选。初始化为:

f[u][0]=0,f[u][1]=su, f[u][0]=0,\qquad f[u][1]=s_u,

其余状态为 −∞-\infty。这里 s0=0s_0=0,所以虚拟根的初值为 f[0][1]=0f[0][1]=0。

不能把“恰好选择 jj 门”写成“至多选择 jj 门”,却仍使用同一套初值。状态数量不足与合法的零收益,是不同的情况。

4 合并孩子

沿用上一篇的逐个合并。设旧部分已经包含 uu 和若干孩子子树,当前合并孩子 vv:

next[a+b]=max⁡(next[a+b],f[u][a]+f[v][b]). next[a+b]=\max\bigl(next[a+b],f[u][a]+f[v][b]\bigr).

其中 a≥1a\ge1、b≥0b\ge0、a+b≤Ka+b\le K。

  • a≥1a\ge1:旧部分已经选择 uu。
  • b=0b=0:当前孩子子树完全不选。
  • b>0b>0:孩子子树方案已经包含 vv,因此选择 vv 所需的直接先修课 uu 也在方案内。

每次合并使用独立的 next 数组,合并后再覆盖旧数组。孩子之间只通过 uu 相连,逐个合并不会破坏依赖,也不会重复选择同一门课程。

这一问题按课程数量分配名额。更一般的“每件物品占用不同容量”的模型,见 有依赖的背包。

5 手算示例

图中的课程信息如下,先修课为 00 表示没有先修课:

课程 直接先修课 学分
1 0 2
2 1 8
3 1 5
4 0 6
5 4 9

以 11 为根的子树,选择 0,1,2,30,1,2,3 门课的最优值分别为 0,2,10,150,2,10,15;以 44 为根的子树,对应 0,1,20,1,2 门课的最优值为 0,6,150,6,15。

现在选 M=3M=3 门真实课程。虚拟根先占一个节点名额,剩余三个分给两棵课程子树:

分给子树 1 分给子树 4 最大学分
0 3 不可行,子树 4 只有两门课
1 2 2+15=172+15=17
2 1 10+6=1610+6=16
3 0 15+0=1515+0=15

答案为 f[0][4]=17f[0][4]=17。如果错误地输出 f[0][3]f[0][3],就只选了两门真实课程。

示例输入输出

输入:

5 3
0 2
1 8
1 5
0 6
4 9

输出:

17

6 子树大小裁剪

合并前,令 A=sz[u]A=sz[u] 为旧部分的节点数,B=sz[v]B=sz[v] 为当前孩子子树的节点数。枚举范围限制为:

1≤a≤min⁡(A,K),0≤b≤min⁡(B,K−a). 1\le a\le\min(A,K),\qquad 0\le b\le\min(B,K-a).

不能让旧部分选择超过 AA 个节点,也不能让孩子子树提供超过 BB 个节点。合并完成后,再令 sz[u]←A+Bsz[u]\gets A+B。

若每次都扫描完整的两个 KK 范围,时间上界为 O(NK2)O(NK^2)。使用上述范围后,可以证明总时间为 O(NK)O(NK),其中 N=n+1N=n+1,包含虚拟根。

先看一个较直观的 O(N2)O(N^2) 上界:忽略名额限制,一次合并的正数数量对 (a,b)(a,b) 至多有 ABAB 个。把各个节点起初看作单点集合,按程序顺序合并;任意两个节点只会在其所属集合首次合并时跨集合配对一次,所以所有 ABAB 之和为 (N2)\binom N2。

这给出的是枚举次数的上界。实际还有 a+b≤Ka+b\le K、不可行状态跳过等限制,不能据此声称代码循环次数始终严格等于点对数。

更紧的 O(NK) 时间界

只考虑 b≥1b\ge1,一次合并的枚举次数不超过 min⁡(A,K)min⁡(B,K)\min(A,K)\min(B,K)。定义:

Φ(s)={s2,s≤K,2Ks−K2,s>K. \Phi(s)=\begin{cases} s^2,&s\le K,\\ 2Ks-K^2,&s>K. \end{cases}

对任意正整数 A,BA,B,有:

min⁡(A,K)min⁡(B,K)≤Φ(A+B)−Φ(A)−Φ(B). \min(A,K)\min(B,K)\le\Phi(A+B)-\Phi(A)-\Phi(B).

可以按是否超过 KK 验证:两者之和不超过 KK 时,右侧为 2AB2AB;两者都至少为 KK 时为 K2K^2;一大一小时为 2KB−B2≥KB2KB-B^2\ge KB,其中 B≤KB\le K。最后一种情况是 A,B<K<A+BA,B<K<A+B,右侧为 2AB−(A+B−K)2≥AB2AB-(A+B-K)^2\ge AB,因为 A+B−K≤min⁡(A,B)A+B-K\le\min(A,B)。

从 NN 个单点集合合并到整棵树,所有势能差相加,内部项抵消,总和为 Φ(N)−NΦ(1)≤2NK\Phi(N)-N\Phi(1)\le2NK。

另外,b=0b=0 的处理、数组初始化和复制,每个节点或每次孩子合并至多花 O(K)O(K),总计仍为 O(NK)O(NK)。因此完整实现的时间复杂度为 O(NK)O(NK)。

7 正确性

每个真实课程方案加入虚拟根后,都唯一对应一个包含根的合法树上方案,且节点数增加 11、学分不变。

一次合并中,任意合法方案在旧部分和当前孩子子树内的选择,分别对应枚举中的 a,ba,b。若孩子子树非空,其根与先修课 uu 都被选,依赖成立;反过来,任意两个合法子方案也都能这样合并。

按孩子数归纳,合并后保留了各个数量下的最大学分。故 f[0][M+1]f[0][M+1] 恰好是选择 MM 门真实课程的最优值。

8 代码实现

#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];  // 非空方案必须先选子树根 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;
                // a>=1 保证已选 u;b>0 时孩子方案保证已选 v。
                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;  // DP 中把必选的虚拟根也算作一个节点
    for (int u = 1; u <= n; ++u) {
        int parent;
        cin >> parent >> score[u];
        g[parent].push_back(u);  // 无先修课的课程统一接到虚拟根 0
    }

    dfs(0);  // score[0]=0,不增加学分
    cout << f[0][K] << '\n';
    return 0;
}

时间复杂度为 O((n+1)(M+1))O((n+1)(M+1)),空间复杂度相同。原题学分总和不超过 300×20300\times20,使用 int 即可。不可行状态先检查,再进行加法。

9 相关题解

暂无相关题解