1、http://acm.hdu.edu.cn/showproblem.php?pid=1011
2、题目大意;
有n个洞穴，每个洞穴中有相应的价值和bugs,现在有m个士兵，每个士兵可以消灭20个bugs,求这m个士兵最多可以获得多少价值
dp[i][j]表示以i为根用掉j个士兵获得的最大价值
dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
3、AC代码：
#include<stdio.h>
#include<algorithm>
using namespace std;
#include<string.h>
#include<vector>
#define N 105
vector<int> adj[N*2];
int dp[N][N];
int w[N],val[N],vis[N],m;
void dfs(int u)
{vis[u]=1;for(int i=w[u];i<=m;i++)dp[u][i]=val[u];for(int i=0;i<adj[u].size();i++){int v=adj[u][i];if(vis[v]==0){dfs(v);for(int j=m;j>=w[u];j--){for(int k=1;k<=j-w[u];k++)//k从1开始，从0wrong{dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);}}}}
}
int main()
{int n,a,b;while(scanf("%d%d",&n,&m)!=EOF){if(n==-1 && m==-1)break;for(int i=0;i<=n;i++){adj[i].clear();}memset(dp,0,sizeof(dp));for(int i=1;i<=n;i++){scanf("%d%d",&w[i],&val[i]);w[i]=(w[i]+19)/20;//dp[i][w[i]]=val[i];}for(int i=1;i<n;i++){scanf("%d%d",&a,&b);adj[a].push_back(b);adj[b].push_back(a);}memset(vis,0,sizeof(vis));//注意m==0否则wrongif(m==0) {printf("0\n");continue;}dfs(1);
// for(int i=1;i<=m;i++)
// printf("%d\n",dp[1][i]);printf("%d\n",dp[1][m]);}return 0;
}