hdu 1561 The more, The Better 背包型树形DP 简单题

　　　　　　　　　　　　　　　　The more, The Better

Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 6324 Accepted Submission(s): 3722

Problem Description

ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗？

Input

每个测试实例首先包括2个整数，N,M.(1 <= M <= N <= 200);在接下来的N行里，每行包括2个整数，a,b. 在第 i 行，a 代表要攻克第 i 个城堡必须先攻克第 a 个城堡，如果 a = 0 则代表可以直接攻克第 i 个城堡。b 代表第 i 个城堡的宝物数量, b >= 0。当N = 0, M = 0输入结束。

Output

对于每个测试实例，输出一个整数，代表ACboy攻克M个城堡所获得的最多宝物的数量。

Sample Input

3 2

0 1

0 2

0 3

7 4

2 2

0 1

0 4

2 1

7 1

7 6

2 2

0 0

Sample Output

5 13

Author

8600

Source

HDU 2006-12 Programming Contest

当可以直接攻克城堡i时，我们认为先要攻克城堡0，才可以选择去攻克城堡i

则这道题的图就变成了一棵有根树，root=0

我们发现，这道题和POJ1155是差不多的，区别在于：

1155我们只把叶子节点看成是背包

而这道题，我们把每一个节点都看成是一个背包

既然是背包，那么现在就是要拿哪些背包(节点)的问题了。

dp[i][j] 表示以节点i为根的子树中，拿j个背包的最大收益

dp初始化为-inf

则我们要拿节点v，则必须拿节点father(v)

则肯定有：

dp[i][0]=0

dp[i][1]=cost[i]

dp[i][j>1]时，必须拿节点i这一个背包，剩下的j-1个背包再从节点i的儿子节点所在的子树中拿

那么递推式就出来了

j-k>=1时，dp[i][j]=max(dp[i][j],dp[i][j-k]+dp[son][k])

(j-k>=1保证了当前子树根节点i这个背包一定会被拿到)

注意递推时候j，k的递推顺序

  1 #include<cstdio>
  2 #include<cstring>
  3 
  4 using namespace std;
  5 
  6 inline int max(int a,int b)
  7 {
  8     return a>b?a:b;
  9 }
 10 
 11 const int maxn=205;
 12 const int inf=0x3f3f3f3f;
 13 
 14 int dp[maxn][maxn];
 15 int cost[maxn];
 16 int siz[maxn];
 17 int out[maxn];
 18 struct Edge
 19 {
 20     int to,next;
 21 };
 22 Edge edge[maxn];
 23 int head[maxn];
 24 int tot;
 25 
 26 void addedge(int u,int v)
 27 {
 28     edge[tot].to=v;
 29     edge[tot].next=head[u];
 30     head[u]=tot++;
 31 }
 32 
 33 void init(int n)
 34 {
 35     memset(head,-1,sizeof head);
 36     tot=0;
 37     memset(out,0,sizeof out);
 38     for(int i=0;i<=n;i++)
 39     {
 40         dp[i][0]=0;
 41         for(int j=1;j<=n;j++)
 42             dp[i][j]=-inf;
 43     }
 44 }
 45 
 46 void solve(int ,int );
 47 void dfs(int );
 48 
 49 int main()
 50 {
 51     int n,m;
 52     while(~scanf("%d %d",&n,&m))
 53     {
 54         if(!n&&!m)
 55             break;
 56         init(n);
 57         cost[0]=0;
 58         for(int i=1;i<=n;i++)
 59         {
 60             int u;
 61             scanf("%d %d",&u,&cost[i]);
 62             addedge(u,i);
 63             out[u]++;
 64         }
 65         solve(n,m);
 66     }
 67     return 0;
 68 }
 69 
 70 void solve(int n,int m)
 71 {
 72     dfs(0);
 73     printf("%d
",dp[0][m+1]);
 74     return ;
 75 }
 76 
 77 void dfs(int u)
 78 {
 79     siz[u]=1;
 80     for(int i=head[u];~i;i=edge[i].next)
 81     {
 82         int v=edge[i].to;
 83         if(!out[v])
 84         {
 85             dp[v][0]=0;
 86             dp[v][1]=cost[v];
 87             siz[v]=1;
 88         }
 89         else
 90         {
 91             dfs(v);
 92         }
 93         siz[u]+=siz[v];
 94         dp[u][1]=cost[u];
 95         for(int j=siz[u];j>=2;j--)
 96         {
 97             for(int k=0;k<=siz[v];k++)
 98                 if(j-k>=1)
 99                     dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
100         }
101     }
102 }

View Code