hdu 1561 The more, The Better (樹形背包dp)

題目鏈接:   hdu-1561

題目
ACboy很喜歡玩一種戰略游戲，在一個地圖上，有N座城堡，每座城堡都有一定的寶物，在每次游戲中ACboy允許攻克M個城堡並獲得裡面的寶物。但由於地理位置原因，有些城堡不能直接攻克，要攻克這些城堡必須先攻克其他某一個特定的城堡。你能幫ACboy算出要獲得盡量多的寶物應該攻克哪M個城堡嗎？

思路
簡單樹形背包dp,當作樹形背包的第一道入門題非常合適

題目給的是森林,那麼給增加一個"根節點", 指向森林中的每個樹的根節點
f(i, j)表示子樹i, 取j個城堡寶藏的時候的最大值
i的每個子節點表示的子樹可以看作是一組物品,在這個子樹上可以選擇取1,2,3...j-1個的城堡寶藏
那麼就是等價於對每個子節點做分組背包.

f(i, j) = max{ max{f(i, j-k)+f(v, k) | 1<=k<j }  |  v是i的子樹  }

因為增加了一個根節點,而且拿子節點之前必須先拿父節點,所以m值要增加1,用來拿根節點.

有個優化, 對於某個子樹,它取的個數不可能超過這個子樹的節點數,優化了可以到0MS

代碼

  /**===================================================== *  
 This is a solution for ACM/ICPC problem * *   @source     
 : hdu-1561 The more, The Better * 
  @description : 樹形背包dp * 
  @author      : shuangde *   @blog      
  : blog.csdn.net/shuangde800 *   @email   
    : zengshuangde@gmail.com *  
 Copyright (C) 2013/08/20 11:27 All rights reserved. 
 *======================================================*/
#include <iostream>#include
 <cstdio>#include 
<algorithm>#include <vector>
#include <queue>
#include <cmath>
#include <cstring>
#define MP make_pairusing namespace std;
typedef pair<int, int >PII;
typedef long long int64;
const int INF = 0x3f3f3f3f;
const double PI  = acos(-1.0);
const int MAXN = 210;vector<int>adj[MAXN];
int val[MAXN];
int tot[MAXN];
int f[MAXN][MAXN];
int n, m;
int dfs(int u) {    f[u][1] = val[u];
    tot[u] = 1;  
  for (int i = 0; i < adj[u].size(); 
++i) {        int v = adj[u][i];   
     tot[u] += dfs(v);   
 }    for (int i = 0; i < adj[u].size(); 
++i) {        int v = adj[u][i];       
 for (int s = tot[u]>m?m:tot[u]; s >= 1; 
--s) {            for (int j = 1;
 j < s && j <= tot[v]; 
++j) {                f[u][s] = max(f[u][s], f[u][s-j] + f[v][j]);   
          }        }    }    return tot[u];
}int main(){    while (~scanf("%d %d", &n, &m) && n + m) {        // init        for (int i = 0;
 i <= n; ++i)            adj[i].clear();   
     val[0] = 0;   
     for (int i = 1; i <= n; ++i) {            int a; 
           scanf("%d %d", &a, &val[i]);     
       if (a) {                adj[a].push_back(i);    
         } else {                adj[0].push_back(i);   
          }        }        memset(f, 0, sizeof(f));   
     ++m;        dfs(0);    
    printf("%d\n", f[0][m]);  
  }    return 0;}