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];
}