hdu 1011 Starship Troopers

本文从WordPress迁移而来, 查看全部WordPress迁移文章

树dp 背包

题意:网上的题意都没几个人写得清楚的…..给一个无根树,每个点有a个bug,b价值,你从点1出发。有m个工具,每个工具可以去除20个bug。你必须去掉当前点的bug,才能继续走下去(),去掉一个点的bug,一定要>=点的bug,好像20个bug,需要1个工具,但是50个bug,是需要3个工具的。另外走下去不是只能走一条路径,而是可以分叉的,你用工具去除bug,工具就会消失掉,以后不能再用。注意一些点是无bug而且有价值的,这些点只需要获取价值不需要花费工具。另外题目规定了,如果是工具数为0,直接输出0。问最终可以获得的最大价值

注意一点,一个点一定要消除完bug了,才能继续走下去,而且可以分支走

dp[u][m]表示分配m个工具到u的子树下,能获得的最大价值

dp[u][j] = max( dp[u][j-k] + dp[v][k] );

注意 k <= j - cost[u]; cost[u]表示点u需要多少工具,因为一定要消除u的bug才能走向v,所以已经用掉了cost[u]个工具

边界,一开始只考虑去除点u的bug时,dp[u][cost[u] ….. m] = val[u];

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 110
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

int n,m;
vector<int>e[N];
int cost[N],val[N];
int dp[N][N];

void dfs(int u,int fa){
for(int i = m; i >= cost[u]; i--)
dp[u][i] = val[u];
for(int i = 0 ; i < e[u].size(); i++){
int v = e[u][i];
if(v == fa) continue;
dfs(v,u);
}
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(v == fa) continue;
for(int j = m; j >= cost[u]; j--)
for(int k = 1; k <= j-cost[u]; k++){
dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[v][k]);
}
}
}

int main(){
while(scanf("%d%d",&n,&m)!=EOF){
if(n == -1 && m == -1) break;
for(int i = 1; i <= n; i++)
e[i].clear();
for(int i = 1; i <= n; i++){
int c,v;
scanf("%d%d",&c,&v);
val[i] = v; cost[i] = (c+19)/20;
}
for(int i = 1; i < n; i++){
int u,v;
scanf("%d%d",&u,&v);
e[u].pb(v); e[v].pb(u);
}
if(!m) { puts("0"); continue; }
cl(dp,0);
dfs(1,-1);
printf("%d\n",dp[1][m]);
}
return 0;
}