AK-dream

选课[luogu P2014]

AK-dream

发布于：2020年3月5日
次浏览

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

【输入格式】
第一行有两个整数$N$,$M$用空格隔开。($1 \leq N \leq 300$,$1 \leq M \leq 300$)

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

【输出格式】
只有一行，选$M$门课程的最大得分。

题解

可以看出如果将课程向它的先修课连边 会形成一棵树 其中$0$号节点就是根

显然是一个背包问题。。。外面再套一个树形DP

先令$f[x][i][j]$表示$x$的子树中 枚举到$x$的第$i$个儿子 在$x$的子树中一共选了$j$个节点 的最大学分

从一个儿子的子树里按规则取$k$个节点出来就相当于一个重量为$k$，权值为$f[son][子树大小][k]$的物品 显然你从一个儿子那里只能选择一个这样的物品 你不可能既从这个儿子的子树中选取3个节点 又再选取重复的2个节点 所以实际上就是一个分组背包 一个组就是一个儿子的子树

那么转移方程是$f[x][i][j]=\min_{k=1}^{j-1}(f[x][i-1][j],f[x][i-1][j-k]+f[son[i]][tot][k])$
$son[i]$就是$x$的第$i$个儿子$tot$就当是$son[i]$的子树大小吧

初始状态：$dp[x][0][1] = s_x$其他的都设成$-inf$

根据背包DP的尿性$i$那一维是可以通过倒着枚举来优化掉，降低空间复杂度的(虽然不优化也没事)。。。

时间复杂度大大低于$O(n^3)$

代码

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
45
46
#include <bits/stdc++.h>
using namespace std;

inline int read() {
	int x = 0, f = 1; char ch = getchar();
	for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1;
	for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 1) + (x << 3) + (ch ^ '0');
	return x * f;
}

int n, m;

int head[305], pre[605], to[605], sz;
int a[305], f[305][305];

inline void addedge(int u, int v) {
	pre[++sz] = head[u]; to[sz] = v; head[u] = sz;
	pre[++sz] = head[v]; to[sz] = u; head[v] = sz;
} 

void dfs(int x, int fa) {
	f[x][1] = a[x];
	for (int i = head[x]; i; i = pre[i]) {
		int y = to[i];
		if (y == fa) continue;
		dfs(y, x);
		for (int j = m; j >= 1; j--) {
			for (int k = 0; k < j; k++) {
				f[x][j] = max(f[x][j], f[y][k] + f[x][j-k]);
			}
		}
	}
}

int main() {
	n = read();
	m = read() + 1; 
	for (int i = 1; i <= n; i++) {
		addedge(read(), i);
		a[i] = read();
	}
	memset(f, -0x3f, sizeof(f));
	dfs(0, 0);
	printf("%d\n", f[0][m]);
	return 0;
}

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：http://akdream.tk/post/344cbb83.html/

更新于：2020年9月7日

动态规划

树形DP

评论