HDU 1561 - The more, The Better

HDU 1561 - The more, The Better

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

http://blog.csdn.net/woshi250hua/article/details/7637847

解题思路：和Poj1155、1947一样，都是在树形结构上进行分组背包处理。本题的依赖关系可以理解成树边，到达子节点必须先经过父节点，本质是一样的，这样可以建立起一个森林，如果为每棵树的添加一个公共父节点0那就成了一棵树了，这是个实用性很强的小技巧。建立起一棵树就开始如何进行dp，如何从子节点获取信息。

    一个子节点就可以返回m个状态，每个状态表示容量为j（j<=m)时选最多的宝物，而一个子节点中只可以选择一个状态进行转移，每个节点有若干个子节点，问题就转换为分组背包，几个子节点就是几个分组背包，体积是选几个地点，价值是宝物价值。

     状态转移方程: dp[v][1] = Money[v]; (v为叶子节点)
                          dp[v][j] = max(dp[v][j],dp[v][j-i] + dp[k][i] );(v为非叶子节点,j表示用户个数,i为容量，k为v的子节点,)
    算法复杂度O(sum(num[i],num[s])) (num[i]为某个节点的叶子子孙个数，num[s]为i的子节点的叶子子孙个数)

    本题加了个剪枝，每次转移时不必都从最大容量m开始，而可以把当前可能转移的最大容量算出来进行转移，最大容量就是子节点个数，速度快了10几倍。

以树来存储各城堡之间的依赖关系。

首先说状态表示，dp[i][j]表示在以i为根节点的子树上攻破j个城堡可达到的最大收益。

为方便表示，以0号节点为总的根节点。

http://blog.csdn.net/harrypoirot/article/details/25426315

1. vector<int>   map[205];  
2. int val[205],dp[205][205];  
3. int n,m;  
4. //dp[i][j]:以第i个节点为起始，攻击j次的最大获益  
5.   
6. inline int bet(int x,int y)  
7. {  
8.     if(x>y)  return x;  
9.     return y;  
10. }  
11. void dfs(int bg,int c)  
12. {  
13.     int size=map[bg].size();  
14.     dp[bg][1]=val[bg];//只攻击该节点  
15.       
16.     for(int i=0;i<size;++i)//对于bg的所有子节点做01背包  
17.     {  
18.         if(c>1)  dfs(map[bg][i],c-1);  
19.         //若未到最后，则继续向下深搜,先算好将来所需的数据  
20.   
21.         for(int j=c;j>1;--j)//当背包容量为c时，j=1时为只选bg  
22.         {  
23.             for(int k=0;k<=j-1;++k)  
24.             {  
25.                 //攻击了第i个子节点下的k个节点,那么还剩下j-k次机会攻击其余的  
26.                 dp[bg][j]=bet(dp[bg][j],dp[bg][j-k]+dp[map[bg][i]][k]);  
27.             }  
28.         }  
29.     }  
30. }  
31.   
32. int main()  
33. {  
34.     while(cin>>n>>m)  
35.     {  
36.         if(n==0&&m==0)  break;  
37.   
38.         memset(val,0,sizeof(val));  
39.         memset(dp,0,sizeof(dp));  
40.         for(int i=0;i<=n;++i)    map[i].clear();  
41.         int a,b;  
42.         for(int i=1;i<=n;++i)  
43.         {  
44.             scanf("%d%d",&a,&b);  
45.             map[a].push_back(i);  
46.             val[i]=b;  
47.         }  
48.   
49.         dfs(0,m+1);//从‘0’开始  
50.         cout<<dp[0][m+1]<<endl;  
51.     }  
52. }  
53. 
    

http://blog.csdn.net/me4546/article/details/6612253

1. /* 
2.  
3. dp[i][j]代表以i为根节点，一共选取j个节点所取得的最大价值，i这个节点一定要选 
4. dp_temp[i][j]代表以i为根节点，一共选取j个节点所取得的最大价值，i这个节点一定不选 
5.  
6. 那么   dp[i][j+1]=dp_temp[i][j]+val[i]; 
7.          dp_temp[i][j+k]=max(dp_temp[i][j+k],dp_temp[i][j]+dp[son[i]][k]); 
8.          
9. 解释一下 dp_temp[i][j]+dp[son[i]][k]，其中 son[i]代表i这个节点的孩子节点， 
10.          假设son[i]这个节点中存在选取K个节点这个状态，那么这个孩子节点就 
11.          可以向dp_temp[i][j+k]转移，因为转移的时候都是从孩子转移过来的， 
12.          那么要是选择了son[i]这个节点，这个节点本身是一定要选择的， 
13.          所以转移方程不是 + dp_temp[son[i]][k],而是 +dp[son[i]][k]  
14.           
15. */
16. vector<int> E[N];  
17. int dp_temp[N][N],dp[N][N];  
18. int val[N],n,m;  
19. bool h[N];  
20.   
21. void init(int n){  
22.     val[0]=0;  
23.     for(int i=0;i<=n;i++)  
24.         E[i].clear();  
25.     memset(h,0,sizeof(h));  
26.     memset(dp,-1,sizeof(dp));  
27.     memset(dp_temp,-1,sizeof(dp_temp));  
28. }  
29.   
30. void dfs(int u){  
31.     if(h[u]) return;  
32.     h[u]=1;  
33.     dp_temp[u][0]=0;  
34.     for(int i=0;i<E[u].size();i++){  
35.         int v=E[u][i];  
36.         if(!h[v])  
37.             dfs(v); //叶子节点未访问过则继续访问   
38.         for(int j=m;j>=0;j--)  
39.             for(int k=1;k+j<=m;k++)  
40.                 if(dp_temp[u][j]!=-1&&dp[v][k]!=-1){  
41.                     if(dp_temp[u][j+k]<dp_temp[u][j]+dp[v][k])  
42.                         dp_temp[u][j+k]=dp_temp[u][j]+dp[v][k];  
43.                 }  
44.     }  
45.     for(int i=0;i<=m;i++)  
46.         if(dp_temp[u][i]!=-1)  
47.             dp[u][i+1]=dp_temp[u][i]+val[u];  
48. }  
49. int main(void){  
50.     while(scanf("%d%d",&n,&m),n||m){  
51.         init(n);  
52.         for(int i=1;i<=n;i++){  
53.             int u;  
54.             scanf("%d%d",&u,&val[i]);  
55.             E[u].push_back(i);  
56.         }  
57.         dfs(0);  
58.         printf("%d\n",dp[0][m+1]);  
59.     }  
60. }  

还有一种直接一个数组