HIGH92 最大学分

题目描述

在大学选课系统中，共有 $N$ 门课程，需要从中选出恰好 $M$ 门。每门课程 $i$ 有 $s_i$ 的学分和至多一门直接先修课 $p_i$ 。

选课必须满足先修课约束，即要选修一门课程，必须先选修它的直接先修课，以及先修课的先修课，以此类推，直到根课程（没有先修课的课程）。

请求出在满足约束的条件下，选修 $M$ 门课程能获得的最大总学分。

解题思路

这是一个在树形依赖结构上进行选择，以在限定数量下最大化价值的问题。这是一个经典的树形背包（或称树形DP）问题。

1. 模型抽象

图结构: 课程之间的先修关系构成了一个森林（由多棵树组成）。每门没有先修课的课程（ $p_i = 0$ ）是其所在树的根节点。
依赖关系: “选一门课必须选其所有祖先课程”的规则，是树形DP的核心约束。
背包模型: 我们可以将 $M$ 门要选的课程看作是背包的容量，每门课程看作是一个物品。选择一门课程会占用 1 的容量，并获得其学分作为价值。

2. 状态定义

为了处理森林结构，一个常见的技巧是创建一个虚拟的“超级根”节点（编号为0），并将所有原始的根节点（ $p_i=0$ 的课程）作为它的子节点。这样，整个森林就变成了一棵以0为根的单棵树。

我们定义一个二维DP数组： $dp[u][j]$ 表示在以节点 $u$ 为根的子树中，选择 $j$ 门课程（必须包含节点 $u$ 本身）所能获得的最大学分。

3. 状态转移

我们通过一次深度优先搜索 (DFS)，以自底向上（后序遍历）的方式来计算DP值。对于当前节点 $u$ ，我们先递归地计算完它所有子节点 $v$ 的DP值，然后用这些子节点的结果来更新节点 $u$ 的DP值。

初始化: 对于节点 $u$ ，首先我们必须选择它自己，这占用了 1 个名额，获得了 $s_u$ 的学分。所以 $dp[u][1] = s_u$ 。
合并子树: 遍历 $u$ 的每一个子节点 $v$ 。每处理一个子节点，就相当于将子树 $v$ 的选课方案与当前节点 $u$ 已有的方案进行合并。这本质上是一个分组背包的合并过程：
- 外层循环遍历为 $u$ 当前方案分配的名额 $j$ 。
- 内层循环遍历为子树 $v$ 分配的名额 $k$ 。
- 我们将这两个方案合并，形成一个包含 $j+k$ 门课程的新方案，总学分为 $dp[u][j] + dp[v][k]$ 。
- 状态转移方程为： $dp[u][j+k] = \max(dp[u][j+k], dp[u][j] + dp[v][k])$
- 为了确保每个子树的贡献只被计算一次（0/1背包特性），对 $j$ 的循环需要逆序。

4. 最终答案

当整个DFS结束后，我们得到了超级根节点0的DP数组。 $dp[0][j]$ 表示在整个森林中选择 $j$ 门课程（包含虚拟根节点）的最大价值。由于虚拟根节点必须被选，它占用了1个名额，但学分为0。因此，要选 $M$ 门真实课程，对应到DP表中就是选择 $M+1$ 门课程（ $M$ 门真实课程 + 1个虚拟根）。

所以，最终答案就是 $dp[0][M+1]$ 。

代码实现

c++
java
python

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, m;
vector<int> s;
vector<vector<int>> adj;
vector<vector<long long>> dp;
vector<int> sz; // 记录子树大小

void dfs(int u) {
    // 必须选当前课程u
    dp[u][1] = s[u];
    sz[u] = 1;

    for (int v : adj[u]) {
        dfs(v);
        // 将子树v的DP结果合并到u上 (分组背包)
        for (int j = min(m + 1, sz[u]); j >= 1; --j) {
            for (int k = 1; k <= sz[v] && j + k <= m + 1; ++k) {
                if (dp[u][j] != -1 && dp[v][k] != -1) {
                    dp[u][j + k] = max(dp[u][j + k], dp[u][j] + dp[v][k]);
                }
            }
        }
        sz[u] += sz[v];
    }
}

int main() {
    cin >> n >> m;
    s.resize(n + 1, 0);
    adj.resize(n + 1);
    dp.assign(n + 1, vector<long long>(m + 2, -1));
    sz.assign(n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        int p;
        cin >> p >> s[i];
        adj[p].push_back(i); // p=0时，连接到超级根
    }

    dfs(0);

    long long max_credits = dp[0][m + 1];
    cout << (max_credits == -1 ? 0 : max_credits) << endl;

    return 0;
}

import java.util.Scanner;
import java.util.List;
import java.util.ArrayList;
import java.util.Arrays;

public class Main {
    static int n, m;
    static int[] s;
    static List<Integer>[] adj;
    static long[][] dp;
    static int[] sz;

    private static void dfs(int u) {
        // 必须选当前课程u
        dp[u][1] = s[u];
        sz[u] = 1;

        for (int v : adj[u]) {
            dfs(v);
            // 将子树v的DP结果合并到u上
            for (int j = Math.min(m + 1, sz[u]); j >= 1; j--) {
                for (int k = 1; k <= sz[v] && j + k <= m + 1; k++) {
                    if (dp[u][j] != -1 && dp[v][k] != -1) {
                        dp[u][j + k] = Math.max(dp[u][j + k], dp[u][j] + dp[v][k]);
                    }
                }
            }
            sz[u] += sz[v];
        }
    }

    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();

        s = new int[n + 1];
        adj = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            adj[i] = new ArrayList<>();
        }
        dp = new long[n + 1][m + 2];
        for(long[] row : dp) {
            Arrays.fill(row, -1);
        }
        sz = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            int p = sc.nextInt();
            s[i] = sc.nextInt();
            adj[p].add(i);
        }

        dfs(0);

        long maxCredits = dp[0][m + 1];
        System.out.println(maxCredits == -1 ? 0 : maxCredits);
    }
}

import sys

# 增加递归深度限制
sys.setrecursionlimit(2005)

def dfs(u, s, adj, dp, sz, m):
    # 必须选当前课程u
    dp[u][1] = s[u]
    sz[u] = 1

    for v in adj[u]:
        dfs(v, s, adj, dp, sz, m)
        # 将子树v的DP结果合并到u上
        # 逆序遍历保证0/1背包性质
        for j in range(min(m + 1, sz[u]), 0, -1):
            for k in range(1, sz[v] + 1):
                if j + k <= m + 1:
                    if dp[u][j] != -1 and dp[v][k] != -1:
                        dp[u][j + k] = max(dp[u][j + k], dp[u][j] + dp[v][k])
                else:
                    break
        sz[u] += sz[v]

def main():
    n, m = map(int, input().split())
    
    s = [0] * (n + 1)
    adj = [[] for _ in range(n + 1)]
    for i in range(1, n + 1):
        p, score = map(int, input().split())
        s[i] = score
        adj[p].append(i)

    # dp[u][j]: 以u为根的子树中选j门课（含u）的最大价值
    dp = [[-1] * (m + 2) for _ in range(n + 1)]
    # sz[u]: 以u为根的子树大小
    sz = [0] * (n + 1)

    dfs(0, s, adj, dp, sz, m)

    max_credits = dp[0][m + 1]
    print(max_credits if max_credits != -1 else 0)

if __name__ == "__main__":
    main()

算法及复杂度

算法: 树形DP (树形背包)
时间复杂度: $O(N \cdot M)$ 。看似有三层循环，但对任意一对节点 $(u, v)$ ，当 $u$ 是 $v$ 的祖先时， $v$ 在 $u$ 的子树中，它们的组合只会在合并 $u$ 和包含 $v$ 的那个子树时被计算一次。经过均摊分析，总的时间复杂度为 $O(N \cdot M)$ 。
空间复杂度: $O(N \cdot M)$ 。需要 $O(N)$ 存储树结构，以及 $O(N \cdot M)$ 存储整个DP表。

题解 | #最大学分#

HIGH92 最大学分

题目描述

解题思路

代码实现

算法及复杂度