HDU 1561 The more, The Better / 树形DP

树形DP 选m个节点权值加起来最大

因为可能是森林 就是都没有限制就可以选 去一个超级源点0 这样就是一棵树了

然后就是基础的树形DP了 DP方程很好想 也很好转移

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 210;
struct node
{
	int v, w;
};
vector <node> G[maxn];
int n, m;
int dp[maxn][maxn];
int a[maxn];
int sum[maxn];
void dfs(int u)
{
	sum[u] = 1;
	dp[u][1] = a[u];
	
	for(int i = 0; i < G[u].size(); i++)
	{
		node x = G[u][i];
		int v = x.v;
		dfs(v);
		sum[u] += sum[v];
		int mm = m;
		mm = min(m, sum[u]);
		for(int j = mm+1; j >= 1; j--)
		{
			for(int k = 0; k < j; k++)
			{
				dp[u][j] = max(dp[u][j], dp[u][j-k]+dp[v][k]);
			}
			//printf("%d\n", dp[u][j]);
		}
	}
}
int main()
{
	while(scanf("%d %d", &n, &m) && (n+m))
	{
		for(int i = 0; i <= n; i++)
			G[i].clear();
		for(int i = 1; i <= n; i++)
		{
			int u, v, w;
			scanf("%d %d", &u, &w);
			v = i;
			G[u].push_back((node){v, w});
			a[i] = w;
		}
		memset(dp, 0, sizeof(dp));
		memset(sum, 0, sizeof(sum));
		dfs(0);
		printf("%d\n", dp[0][m+1]);//+1是因为0也算进去了 
	}
	return 0;
}

HDU 1561 The more, The Better / 树形DP,布布扣,bubuko.com

HDU 1561 The more, The Better / 树形DP

原文：http://blog.csdn.net/u011686226/article/details/21748823