POJ 1155 TELE / 树形DP

树形DP 其中有分组背包 第一个循环是每一组 就是以u为根的若干子树 然后第二个循环是枚举背包体积 从大到小 因为是滚动 第三个循环是枚举每一组的物品

3个循环不能颠倒 以为是分组背包 每组的物品只能选一个 具体这题就是子树不能有重叠 每个点不能选多次

#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int maxn = 3010;
struct edge
{
	int u, v, w;
};
vector <edge> G[maxn];
int num[maxn];
int sum[maxn];
int dp[maxn][maxn];
int n, m;
void dfs(int u)
{
	dp[u][0] = 0;
	if(u > n-m)
	{
		sum[u] = 1;
		dp[u][1] = num[u];
		return;
	}
	for(int i = 0; i < G[u].size(); i++)
	{
		edge x = G[u][i];
		int v = x.v;
		dfs(v);
		sum[u] += sum[v];
	}
	
	for(int i = 0; i < G[u].size(); i++)
	{
		edge x = G[u][i];
		int v = x.v;
		for(int j = sum[u]; j >= 0; j--)
		{
			for(int k = 0; k <= sum[v] ; k++)
			{
				if(j < k)
					break;
				dp[u][j] = max(dp[u][j], dp[u][j-k]+dp[v][k]-x.w);
			}
		}
	}
}
int main()
{
	
	while(scanf("%d %d", &n, &m) != EOF)
	{
		for(int i = 1; i <= n; i++)
			G[i].clear();
		for(int i = 1; i <= n-m; i++)
		{
			int t;
			scanf("%d", &t);
			while(t--)
			{
				int v, w;
				scanf("%d %d", &v, &w);
				G[i].push_back((edge){i, v, w});
			}
		}
		memset(sum, 0, sizeof(sum));
		//memset(dp, 0, sizeof(dp));
		for(int i = n-m+1; i <= n; i++)
			scanf("%d", &num[i]);
		for(int i = 0; i <= n; i++)
			for(int j = 0; j <= n; j++)
				dp[i][j] = -999999999;
	
		dfs(1);
		for(int i = n; i >= 0; i--)
		{
			if(dp[1][i] >= 0)
			{
				printf("%d\n", i);
				break;
			}
			//printf("%d\n", dp[1][i]);
		}
	}
	return 0;
}

POJ 1155 TELE / 树形DP,布布扣,bubuko.com

POJ 1155 TELE / 树形DP

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