P2014 选课

P2014 选课

题目链接

这道题目是一个比较简单的树形 (DP) ,有限制的背包问题，转化为树上问题就是要选本节点必须选这棵子树的根节点，最大化价值。

首先，设 (dp[i][j]) 表示枚举到以 (i) 为根的子树中选了 (j) 个节点的所能得到的最大价值。

预处理：(dp[i][1]=val[i]) ，在枚举到 (i) 这棵子树中只选一个节点，所以只能选根节点。

因为用 (0) 节点作为虚根节点，使这个森林成为一棵树，所以可用的空间应该到 (k+1) ，默认根节点必须选。

    转移：
	for (int j=m+1;j>=1;j--)
	{
	    for (int k=0;k<j;k++)
	    dp[x][j]=max(dp[x][j],dp[ed[i].e][k]+dp[x][j-k]);
	}

首先枚举在当前节点为根的子树中用了多少节点，然后枚举当前节点的子树用了多少节点。

(k=0) ,表示不选这棵子树的所有节点及根节点

(k<j) ,因为 (k ot=0) 时默认选根节点，所以可以选的节点数目是 (k-1) 。

一种是保持原来的状态，一种是在当前子树（除根节点外）选 (k) 个节点，取 (max) 。

因为当 (k=1) 的时候就是默认只选子树的根节点，所以不用特判子树的根节点。

// luogu-judger-enable-o2
#include<iostream>
#include<cstdio>
using namespace std;
const int N=3e2+100;
struct edge{
	int s,e,net;
}ed[N];
int n,m,tot;
int dp[N][N];
int head[N];
inline void dfs(int x)
{
	for (int i=head[x];i;i=ed[i].net)
	{
		dfs(ed[i].e);
		for (int j=m+1;j>=1;j--)
		{
			for (int k=0;k<j;k++)
			dp[x][j]=max(dp[x][j],dp[ed[i].e][k]+dp[x][j-k]);
		}
	}
	return ;
}
inline void add(int s,int e)
{
	ed[++tot]=(edge){s,e,head[s]};
	head[s]=tot;
	return ;
}
int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		int fa;
		scanf("%d%d",&fa,&dp[i][1]);
		add(fa,i);
	}
	dfs(0);
	printf("%d
",dp[0][m+1]);
	return 0;
}