学步园

树形DP+分组背包

题意：从n座城堡中选m座城堡使财宝总量尽量大。有的城堡需要先攻克其他特定的一座城堡

思路：明显的树形结构，增加一个虚拟的0节点就是一棵树。设状态dp[i][j]为在以i为根的子树上选择j个节点的财富最大值；在非0节点上的其他点都必须选择他自己，所以非0节点从1开始记数。

华丽丽的被卡了一天，即使到现在重写第3次AC了还是不知道为什么错。头疼啊头疼

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAXN = 222;
int head[MAXN];
struct E{
	int v,next;
}edge[222];
int tot;
int dp[MAXN][MAXN];
int n,m;

int max(int a, int b) { return a>b?a:b; }

void add(int a, int b)
{
	edge[tot].next = head[a];
	edge[tot].v = b;
	head[a] = tot ++;
}

void gao(int cur)
{
	if(head[cur] == -1) return ;
	int p;
	int i,j;
	for(p=head[cur]; p!=-1; p=edge[p].next)
	{
		gao(edge[p].v);
		for(i=m; i>=0; i--)
		{
			if(dp[cur][i] < 0) continue;
			for(j=0; i+j<=m; j++)
			{
				if(dp[edge[p].v][j] < 0) continue;
				dp[cur][i+j] = max(dp[cur][i+j], dp[cur][i]+dp[edge[p].v][j]);
			}
		}
	}
}

int main()
{
	int i,a,b;
	while(scanf("%d%d", &n, &m),n||m)
	{
		tot = 0;
		memset(head, -1, sizeof(head));
		memset(dp, -1, sizeof(dp));
		for(i=1; i<=n; i++)
		{
			scanf("%d%d", &a, &b);
			add(a,i);
			dp[i][1] = b;
		}
		dp[0][0] = 0;
		gao(0);
		printf("%d\n", dp[0][m]);
	}
	return 0;
}