hdu 1561 The more, The Better

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

树dp 背包

和hdu 1011一样的题目,这里的花费就是1(注意添加的虚节点0的花费为0),其实和hdu 1011是一样的做法,详细分析搜索博客 hdu 1011

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define N 210
#define cl(xx,yy) memset((xx),(yy),sizeof((xx)))
#define pb push_back

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

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

int main(){
//freopen("case.txt","r",stdin);
while(scanf("%d%d",&n,&m)!=EOF){
if(!n && !m) break;
for(int i = 0; i <= n; i++)
e[i].clear();
cl(inde,0);
cl(dp,0);
cl(val,0);
for(int v = 1; v <= n; v++){
int u;
scanf("%d%d",&u,&val[v]);
if(u){ e[u].pb(v); inde[v]++; }
}
for(int i = 1; i <= n; i++)
if(!inde[i]) e[0].pb(i);
dfs(0);
printf("%d\n",dp[0][m]);
}
return 0;
}