5 10 50 10 40 10 40 20 65 30 70 30 1 2 1 3 2 4 2 5 1 1 20 7 -1 -1
50 7
题目意思：有N 个洞，到达每个洞只有一条路可通，形成一棵树状，每个洞里面有虫守着一定价值东西，现在用M 个士兵去占领洞，只有占了该洞才能得到该洞里的东西，己知每个士兵可以消灭20个虫；只有占了一个洞才能继续前进，否则无法走到子树上的洞；1为入口洞。求M个士兵能得到的最大价值。
这是做的第一道树形DP，看了网上的才解出。 本人的体会就是：必须明白dp每一维数代表的是什么意思，才能解出。
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define P 105
#define M 105
struct tree
{
int k;
int child[105];
}node[105];
int dp[P][M];//用M个骑士去占领以P为根的树，得到的最大价值
int trooperNum,vist[105],useTroop[105],brain[105];
void dfs(int p)
{
vist[p]=1;
for(int u=useTroop[p];u<=trooperNum;u++)//只有先占了树根p，才可以去占子树
dp[p][u]=brain[p];
for(int k=1;k<=node[p].k;k++)
{
int chil=node[p].child[k];//p的子节点
if(vist[chil]) continue;//访问过了就不能重复走，这就是区分根节点与子节点
dfs(chil);
//子树的最大价值只能加一次，反以用01背包的思想从大到小
for(int num=trooperNum;num>=useTroop[p];num--)//用num个骑士占领以p为根的树（有的子树可以不占），更新最大值
for(int chilU=1;chilU<=num-useTroop[p];chilU++)//用chilU个骑士去占领以chil点为根的树，在更新中可占可不占
if(dp[p][num]<dp[p][num-chilU]+dp[chil][chilU])//注意加的是用chilU个骑士占领的以chil点为根的子树的最大值
dp[p][num]=dp[p][num-chilU]+dp[chil][chilU];
}
}
int main()
{
int N,a,b,k;
while(scanf("%d%d",&N,&trooperNum)>0)
{
if(N==trooperNum&&N==-1)
break;
for(int i=1;i<=N;i++)
{
scanf("%d%d",&useTroop[i],&brain[i]);
useTroop[i]=(useTroop[i]+19)/20;
node[i].k=0;
}
for(int i=1;i<N;i++)
{
scanf("%d%d",&a,&b);
node[a].k++; k=node[a].k; node[a].child[k]=b;
node[b].k++; k=node[b].k; node[b].child[k]=a;
}
if(trooperNum==0)//注意这里，在实际中没有人去那么就不可能得到东西
{
printf("0\n"); continue;
}
memset(dp,0,sizeof(dp));
memset(vist,0,sizeof(vist));
dfs(1);
printf("%d\n",dp[1][trooperNum]);
}
}
hdu1011Starship Troopers (树形DP),布布扣,bubuko.com
hdu1011Starship Troopers (树形DP)
原文：http://blog.csdn.net/u010372095/article/details/20779017