题意：输入房间的个数n和现在拥有的人个数m，已知1个人能解决20个bug，下面n行输入房间中的bug数量和能获得的brain数量，就算bug不足20个也必须留一个人，后面n-1行输入房间连通的路径，只有解决了前面房间的bug才能进入下一个房间，求最多能获得的brain数量。
一道背包题目，不断更新数据打出表来，最后输出最大的结果就好，比较特殊的是这个题取东西的顺序是有限制的，所以需要先建树，然后再用背包思想，即可得出答案。
这里打表每一行表示房间坐标，每一列表示在这个人数时所能得到的最大brain值
一开始先都初始化为0
123456789101000000000020000000000300000000004000000000050000000000
从房间1开始进行更新
12345678910100101010101010101020000000000300000000004000000000050000000000
顺着树的路径继续更新
123456789101001010101010101010201010101010101010103000000000040003030303030303050000000000
走到头之后再更新前面最大的 dp[root][j+k]=max(dp[root][j+k],dp[root][j]+dp[e][k])，直到全部更新完
1234567891010010103030303050502010101010404040404030202020202020202020400030303030303030500030303030303030
最后更新出这样一个表来，dp[1][m]则就是要求的最大的brain值了。背包思想倒是会，整个题思路也明白，但是我不会建树= =好吧最后还是跑到discuss里参考了下AC的代码才建出来的树。
DISCUSS:http://acm.hdu.edu.cn/discuss/problem/post/reply.php?action=support&postid=19635&messageid=1&deep=0
另外要注意一点，最后dfs之前要记得对m进行一次判断，如果m=0直接输出0结束这次循环，比如1 0 0 1这组数据结果应该是0要是没加这句结果为1，一开始我就没加结果WA了= =
下面AC代码：
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; int w[105],v[105]; int tr[105][105];//建树 int vis[105];//记录这条路是否已走过 int n,m; int dp[105][105];//记录获得的数量 int max(int a,int b) { return a>b?a:b; } int dfs(int root) { int t,e; int i,j,k; vis[root]=1; t=(w[root]+19)/20;//记录走这个房间需要的最少人数 for(i=t;i<=m;i++) { dp[root][i]=v[root];//先将这一层所能基本获得的初始化 } for(i=1;i<=tr[root][0];i++) { e=tr[root][i];//对要走的上一层进行更新 if(!vis[e]) { dfs(e); for(j=m-1;j>=t;j--) { for(k=1;k<=m-j;k++) { if(dp[e][k]!=0)//如果这一点根本走不到就没必要更新 { dp[root][j+k]=max(dp[root][j+k],dp[root][j]+dp[e][k]); } } } } } return 0; } int main() { int i,j; int a,b; while(scanf("%d%d",&n,&m)!=EOF) { if(n==-1&&m==-1) break; memset(tr,0,sizeof(tr)); memset(vis,0,sizeof(vis)); memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) { scanf("%d%d",&w[i],&v[i]); } for(i=1;i<n;i++) { scanf("%d%d",&a,&b); tr[a][0]++;//记录a房间总共挨着多少房间 tr[a][tr[a][0]]=b;//记录第tr[a][0]条路连接的两个房间 tr[b][0]++; tr[b][tr[b][0]]=a; } if(m==0) { cout<<0<<endl; continue; } dfs(1); cout<<dp[1][m]<<endl; } return 0; }
