洛谷 P2014 [CTSC1997] 选课（树形dp， 分组背包）

[CTSC1997] 选课

题目描述

在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有 $N$ 门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程 a 是课程 b 的先修课即只有学完了课程 a，才能学习课程 b）。一个学生要从这些课程里选择 $M$ 门课程学习，问他能获得的最大学分是多少？

输入格式

第一行有两个整数 $N$ , $M$ 用空格隔开。( $1\le N\le 300$ , $1\le M\le 300$ )

接下来的 $N$ 行,第 $I+1$ 行包含两个整数 $k_i $和 $s_i$, $k_i$ 表示第I门课的直接先修课，$s_i$ 表示第I门课的学分。若 $k_i=0$ 表示没有直接先修课（$1\le k_i\le N$ , $1\le s_i\le 20$）。

输出格式

只有一行，选 $M$ 门课程的最大得分。

样例 #1

样例输入 #1

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

样例输出 #1

13
1

算法竞赛进阶指南，291页
1、 考虑当前节点x， 假如有k个孩子节点，分别是 y[1], y[2], ..., y[k]
	f[x][t] 表示以x为根节点的子树，取t个节点所能获得的最大价值。
	首先，根节点x必须选择，剩下的 t - 1 个节点，从 k 颗子树选择。
	将 k 颗子树看成 k 个组， 第 i 组的第j个物品，体积为j， 价值是 f[y[i]][j].
	问题转化为， k 个组，每一组最多选一个物品 （第 i 组的第j个物品，体积为j， 价值是 f[y[i]][j]） 
	典型的分组背包， 并且每一组只选一件物品。
	
2、 转移方程：
	x 的孩子节点是 y， 对于每一个孩子y， 都满足：
	f[x][j] = max(f[x][j - k] + f[y][k], f[x][j])
	k 取值范围： 0 <= k < j.
	k 最多取值 j - 1, 原因是， 根节点x 必须选。
3、 树的根节点为0， 也选择，因此一共选择 m + 1 个节点。 答案是 f[0][m + 1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14

#include 
using namespace std;
const int MaxN = 400;
vector<int> son[MaxN];
int f[MaxN][MaxN];
int n, m;
int score[MaxN];

void dfs(int x)
{
	int size = son[x].size();
	for(int i = 0; i < size; ++i)
	{
		int y = son[x][i];
		dfs(y);
		for(int j = m + 1; j >= 1; --j)
		{
			for(int k = 0; k < j; ++k)
			{
				f[x][j] = max(f[x][j], f[x][j - k] + f[y][k]);
			}
		}
	}
}

int main()
{
	scanf("%d%d", &n, &m);
	int j;
	for(int i = 1; i <= n; ++i)
	{
		scanf("%d%d", &j, &score[i]);
		son[j].push_back(i);
	}
	// 初始化
	for(int i = 1; i <= n; ++i)
	{
		f[i][1] = score[i]; 
	}
	dfs(0);
	printf("%d\n", f[0][m + 1]);
	return 0;
}

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