【算法竞赛进阶指南】CH5402/洛谷p2014 - 选课 - 树形dp模板题

题目描述 

学校实行学分制。

每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。

学校开设了 N 门的选修课程，每个学生可选课程的数量 M 是给定的。

学生选修了这 M 门课并考核通过就能获得相应的学分。

在选修课程中，有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其他的一些课程的基础上才能选修。

例如《Windows程序设计》必须在选修了《Windows操作基础》之后才能选修。

我们称《Windows操作基础》是《Windows程序设计》的先修课。

每门课的直接先修课最多只有一门。

两门课可能存在相同的先修课。

你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先修条件。

假定课程之间不存在时间上的冲突。

输入格式

输入文件的第一行包括两个整数N、M（中间用一个空格隔开）其中1≤N≤300,1≤M≤N。

接下来N行每行代表一门课，课号依次为1，2，…，N。

每行有两个数（用一个空格隔开），第一个数为这门课先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。

学分是不超过10的正整数。

输出格式

输出一个整数，表示学分总数。

输入样例：

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

输出样例：

1
13

题目分析 

每门课的直接先导只有一个，有些课程需要一定的基础知识，必须在选了其他的一些课程的基础上才能选修，所以要从由课程组成的树中选一条链，没有前导课的课不止一节，那么我们要处理一个森林，但是我们可以用0来把森林连成一棵树，当然题目也提示了若不存在先修课则先修课课号为0

那么我们就可以定义状态了，显然一维是不够的，我们可以定义f[i][j]表示以i为根的树中选j个课程所能拿到的最大学分。

以i为根的树的每个子树有多个状态，选1， 2 ...m - 1个课程，对于一个子树我们只能选择其中一个状态，但是可以同时选择多个子树，因为以i为根的子树相互之间不影响。比如i有三个儿子a, b, c，f[a][1], f[a][2], ..., f[a][m -1]只能选一个，但我们还可以从f[b][1], f[b][2], ..., f[b][m - 1]中选一个，从f[c][1], f[c][2], ..., f[c][m - 1]中选一个。

那么很容易看出这本质上是个分组背包，课程看作物品，体积视为1，学分为价值，背包容量为m，一个子树视为一个组，每个子树只能从中选择一种状态。对于分组背包，我们要先枚举体积（记得逆序，因为需要使用上一次的值进行状态转移），再枚举决策（选择一个子树的哪个状态）

代码 

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
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 310;
int f[N][N], w[N], n, m;
int head[N], nex[N], edge[N], tot;
void add(int u, int v){
edge[++ tot] = v;
nex[tot] = head[u];
head[u] = tot;
}
void dfs(int u){
for (int i = head[u]; ~i; i = nex[i]){
int v = edge[i];
dfs(v);
for (int j = m - 1; j >= 1; -- j){//本质上是个分组背包
for (int k = 1; k <= j; ++ k){
f[u][j] = max(f[u][j], f[u][j - k] + f[v][k]);
}
}
}
for (int i = m; i >= 1; -- i) f[u][i] = f[u][i - 1] + w[u];//以u为根的子树要加上根的学分
}
int main()
{
cin >> n>> m;
memset(head, -1, sizeof(head));
for (int i = 1; i <= n; ++ i){
int p;
scanf("%d %d", &p, &w[i]);
add(p, i);
}
++ m;//dp的结果是包含了课号零的（不存在先导课号的父节点），所以实际dfs时要选m + 1个，所以m要加1
dfs(0);
cout << f[0][m] << endl;
return 0;
}

最后

以上就是呆萌枫叶最近收集整理的关于【算法竞赛进阶指南】CH5402/洛谷p2014 - 选课 - 树形dp模板题的全部内容，更多相关【算法竞赛进阶指南】CH5402/洛谷p2014内容请搜索靠谱客的其他文章。