P2014 [CTSC1997] 选课

题目#

[CTSC1997] 选课#

题目描述#

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

$1 \leq N \leq 300$ , $1 \leq M \leq 300$

题解#

树上 dp + 背包

设f[u][i][j]表示以 u 为根的子树中，前 i 颗 u 的子树，选 j 颗的获得的最大学分

然后发现和 01 背包差不多，只不过需要枚举一下 u 中的每一颗子树选多少 (j 为多少)。

可以滚动数组 + 倒叙循环把空间去一维

问题#

子树选的数目不能等于 q，否则这颗子树的根节点就选不了了，导致后代所有的课都选不了（行 48）

代码#

#include<bits/stdc++.h>

using namespace std;

int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}

const int N = 310;

int n, m;

int s[N], size[N];

int head[N], nxt[N], to[N], cnt = 1;

int f[N][N];//表示以u为子树中选m个学科最多能获得多少学分 

void add(int x, int y)
{
	nxt[++cnt] = head[x];
	to[cnt] = y;
	head[x] = cnt;
}

void dfs(int u)
{
	for(int i = head[u]; i; i = nxt[i])
	{
		int v = to[i];
		dfs(v);
		for(int q = m;q >= 0;q--)
		{
			for(int k = 0;k < q/*子树选的数目不能等于q，否则这颗子树的根节点就选不了了，导致后代所有的课都选不了*/;k++)
			{
				f[u][q] = max(f[u][q], f[v][k] + f[u][q - k]);
			}
		}
	}
}

int main()
{
	n = read(), m = read() + 1;

	int anc;

	for(int i = 1;i <= n;i++)
	{
		anc = read();
		s[i] = read();
		add(anc, i);
		f[i][1] = s[i];
	}
	dfs(0);
	cout << f[0][m];
}