洛谷 P2014 分析（别看）

科技起源的小号1

2026-10-16 20:46:45

发布于：天津

1阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个最大值

1.2 题目背景、允许、禁止与限制

背景：
有 $n$ 门功课，每门课有对应的学分 $s_i$ ，每一门课有一门或零门先修课（当 $a$ 是 $b$ 的先修课时，只有先学习 $a$ 才能学习 $b$ ）
允许：
在 $n$ 门功课中选择 $m$ 门学习，问获得的最大学分
限制：
学习的课程必须满足先修课的限制

1.3 题目数据范围与猜测

$1 \le n,m \le 300 \longrightarrow O(nm^2)$

1.4 一句话概括题意

有一个森林
因为发现有些课没有先修课，那么是可以直接选择的，所以都需要与超级源点进行关系的建立
在森林中有先后选择的限制情况下最大化选 $m+1$ 门课的总权值
为什么是 $m+1$ ？因为超级源点是一定要选的，否则其他所有课都无法选，但超级源点选上就会使选课数 $m$ 变为 $m+1$

2 题目破题推导

2.1 第一步：分情况讨论

对于每个节点 $u$ ，在其子树内，选了 $j$ 门课时：

只选 $u$ 自己
选 $u$ 自己 $+$ 从所有子节点 $v$ 对应的子树里选若干门课的学分

2.2 第二步：限制思想

当节点 $u$ 的子树之内选了 $j$ 门课时，每个子节点 $v$ 可以分配多少门课呢？
可以是 $i(i\in[0,j-1])$ 门，因为必须要留一门给 $u$ ，当然所有子节点的课数总和应该是 $j+1$

3 模型匹配

关键词：树形结构，动态求取最大值 $\longrightarrow$ $\huge{树形dp（背包问题）}$

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

int n, m;
const int N = 333;
int s[N];
vector<int> g[N];
int dp[N][N];
void dfs(int u){
	dp[u][1] = s[u];
	for (int i = 0;i < g[u].size();i++){
		int now = g[u][i];
		dfs(now);
	}
	for (int i = 0;i < g[u].size();i++){
		int now = g[u][i];
		for (int j = m;j > 0;j--){
			for (int k = 0;k < j;k++){
				dp[u][j] = max(dp[u][j], dp[now][k] + dp[u][j - k]);
			}
		}
	}
}

int main(){
	
	cin >> n >> m;
	m++;// 超级源点要单独计算+1
	for (int i = 1;i <= n;i++){
		int k;
		cin >> k;
		cin >> s[i];
		g[k].push_back(i);
	} 
	dfs(0);
	cout << dp[0][m];
	
	return 0;
}