题目链接

最大学分

题目描述

有 门课程和 个选课名额。每门课程 有一个学分 和至多一门直接先修课 。如果 则表示没有先修课。选修一门课程必须先选修其所有的先修课程（即所有祖先课程）。 你需要从 门课程中恰好选出 门，要求满足所有先修课约束，并使得所选课程的总学分最大。

输入:

  • 第一行输入两个整数 ，分别表示课程总数与需选课程数。
  • 接下来 行，每行输入两个整数 ，分别表示第 门课程的先修课和学分。

输出:

  • 输出一个整数，代表能取得的最大学分。

解题思路

这个问题的本质是在一个森林结构的依赖关系上，选择固定数量的节点，以获取最大权重。这是一个典型的树形DP问题，并结合了分组背包的思想。

  1. 构建森林:

    • 课程之间的先修关系构成了一个森林（多棵树的集合）。每门没有先修课（）的课程都是一棵树的根节点。我们可以通过邻接表来表示这个森林结构。

  2. 树形DP:

    • 我们需要对森林中的每一棵树进行动态规划。
    • 状态定义: 表示在以节点 为根的子树中，选择 门课程（必须包含 本身）所能获得的最大学分。
    • 状态转移: 我们使用深度优先搜索（DFS）进行后序遍历来计算DP值。对于一个节点 ：
      • 基础情况: 首先选择 本身，所以 。
      • 合并子树: 遍历 的每一个子节点 。在 dfs(v) 调用返回后，我们得到了子树 的所有DP值 。现在，我们需要将这些信息合并到 中。这个合并过程类似一个背包问题：
        • 从 的当前状态（已合并之前的子树）中选出 门课，再从子树 中选出 门课，总共就是 门课。
        • 状态转移方程为：
        • 为避免一次合并中的数据污染，我们需要逆序遍历 。

  3. 分组背包:

    • 在对森林中所有的树都进行过树形DP后，问题就转化为了一个分组背包问题。
    • 分组: 每一棵树都是一个“物品组”。
    • 物品: 在代表树（根为 ）的物品组中，有多种“物品”可供选择：”从该树中选1门课“，”从该树中选2门课“，...，”从该树中选 门课“。选择 门课的”体积“是 ，”价值“是 。
    • 目标: 我们有一个容量为 的背包，需要从这些物品组中各选至多一个物品，使得总体积恰好为 ，且总价值最大。
    • 我们定义一个 数组，表示选 门课能获得的最大总学分，然后用标准的分组背包方法来填充这个数组。

最终， 就是我们要求的答案。

代码

#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> subtree_size;

void dfs(int u) {
    // 初始化当前节点：选择 u 自己，花费1个名额，获得 s[u-1] 学分
    subtree_size[u] = 1;
    dp[u][1] = s[u - 1]; 

    // 遍历子树，合并结果
    for (int v : adj[u]) {
        dfs(v);
        // 将子树 v 的结果合并到 u 上，这是一个背包问题
        // 从后往前遍历j，避免本次更新影响后续决策
        for (int j = min(M, subtree_size[u]); j >= 1; --j) {
            for (int k = 1; k <= min(M - j, subtree_size[v]); ++k) {
                dp[u][j + k] = max(dp[u][j + k], dp[u][j] + dp[v][k]);
            }
        }
        subtree_size[u] += subtree_size[v];
    }
}

int main() {
    cin >> N >> M;
    s.resize(N);
    adj.resize(N + 1);
    vector<int> roots;
    
    for (int i = 1; i <= N; ++i) {
        int p;
        cin >> p >> s[i - 1];
        if (p == 0) {
            roots.push_back(i);
        } else {
            adj[p].push_back(i);
        }
    }

    // dp[u][j] 表示在以 u 为根的子树中，选择 j 门课能获得的最大学分
    dp.assign(N + 1, vector<long long>(M + 1, 0));
    subtree_size.assign(N + 1, 0);

    // 对森林中的每棵树进行树形DP
    for (int root : roots) {
        dfs(root);
    }
    
    // 将多棵树的结果合并，这是一个分组背包问题
    // final_dp[j] 表示选择 j 门课的最大总学分
    vector<long long> final_dp(M + 1, 0);
    for (int root : roots) {
        // 从后往前遍历背包容量
        for (int j = M; j >= 1; --j) {
            // 在以 root 为根的树中选择 k 门课
            for (int k = 1; k <= min(j, subtree_size[root]); ++k) {
                 final_dp[j] = max(final_dp[j], final_dp[j - k] + dp[root][k]);
            }
        }
    }

    cout << final_dp[M] << "\n";
    return 0;
}

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

public class Main {
    static int N, M;
    static int[] s;
    static List<List<Integer>> adj;
    static long[][] dp;
    static int[] subtreeSize;

    public static void dfs(int u) {
        // 初始化当前节点
        subtreeSize[u] = 1;
        dp[u][1] = s[u - 1];

        for (int v : adj.get(u)) {
            dfs(v);
            // 合并子树 v 的结果
            for (int j = Math.min(M, subtreeSize[u]); j >= 1; j--) {
                for (int k = 1; k <= Math.min(M - j, subtreeSize[v]); k++) {
                    dp[u][j + k] = Math.max(dp[u][j + k], dp[u][j] + dp[v][k]);
                }
            }
            subtreeSize[u] += subtreeSize[v];
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        s = new int[N];
        adj = new ArrayList<>(N + 1);
        for (int i = 0; i <= N; i++) {
            adj.add(new ArrayList<>());
        }
        List<Integer> roots = new ArrayList<>();

        for (int i = 1; i <= N; i++) {
            int p = sc.nextInt();
            s[i - 1] = sc.nextInt();
            if (p == 0) {
                roots.add(i);
            } else {
                adj.get(p).add(i);
            }
        }

        dp = new long[N + 1][M + 1];
        subtreeSize = new int[N + 1];

        // 对每棵树进行树形DP
        for (int root : roots) {
            dfs(root);
        }

        // 分组背包
        long[] finalDp = new long[M + 1];
        for (int root : roots) {
            for (int j = M; j >= 1; j--) {
                for (int k = 1; k <= Math.min(j, subtreeSize[root]); k++) {
                    finalDp[j] = Math.max(finalDp[j], finalDp[j - k] + dp[root][k]);
                }
            }
        }

        System.out.println(finalDp[M]);
    }
}

import sys

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

def dfs(u):
    # 初始化当前节点
    subtree_size[u] = 1
    dp[u][1] = s[u - 1]
    
    # 遍历子节点
    for v in adj[u]:
        dfs(v)
        # 合并子树v的结果（背包）
        for j in range(min(M, subtree_size[u]), 0, -1):
            for k in range(1, min(M - j, subtree_size[v]) + 1):
                dp[u][j + k] = max(dp[u][j + k], dp[u][j] + dp[v][k])
        subtree_size[u] += subtree_size[v]

# 读取输入
N, M = map(int, input().split())
s = [0] * N
adj = [[] for _ in range(N + 1)]
roots = []

for i in range(1, N + 1):
    p, credit = map(int, input().split())
    s[i - 1] = credit
    if p == 0:
        roots.append(i)
    else:
        adj[p].append(i)

# dp[u][j]：在以u为根的子树中选j门课（含u）的最大价值
dp = [[0] * (M + 1) for _ in range(N + 1)]
subtree_size = [0] * (N + 1)

# 对森林中的每棵树进行树形DP
for root in roots:
    dfs(root)

# 将多棵树的结果合并（分组背包）
final_dp = [0] * (M + 1)
for root in roots:
    for j in range(M, 0, -1):
        for k in range(1, min(j, subtree_size[root]) + 1):
            final_dp[j] = max(final_dp[j], final_dp[j - k] + dp[root][k])

print(final_dp[M])

算法及复杂度

  • 算法：树形DP + 分组背包
  • 时间复杂度： - 树形DP部分，对每个节点的子树合并操作的复杂度与 相关，总复杂度为 。后续的分组背包复杂度也在此范围内。
  • 空间复杂度： - 主要开销来自存储树形DP结果的 二维数组。