POJ 1155 TELE / 樹形DP

樹形DP 其中有分組背包 第一個循環是每一組 就是以u為根的若干子樹 然後第二個循環是枚舉背包體積 從大到小 因為是滾動 第三個循環是枚舉每一組的物品

3個循環不能顛倒 以為是分組背包 每組的物品只能選一個 具體這題就是子樹不能有重疊 每個點不能選多次

#include 
#include 
#include 
using namespace std;
const int maxn = 3010;
struct edge
{
	int u, v, w;
};
vector  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;
}