題干：

ACboy很喜歡玩一種戰(zhàn)略游戲，在一個(gè)地圖上，有N座城堡，每座城堡都有一定的寶物，在每次游戲中ACboy允許攻克M個(gè)城堡并獲得里面的寶物。但由于地理位置原因，有些城堡不能直接攻克，要攻克這些城堡必須先攻克其他某一個(gè)特定的城堡。你能幫ACboy算出要獲得盡量多的寶物應(yīng)該攻克哪M個(gè)城堡嗎？?

Input

每個(gè)測(cè)試實(shí)例首先包括2個(gè)整數(shù)，N,M.(1 <= M <= N <= 200);在接下來(lái)的N行里，每行包括2個(gè)整數(shù)，a,b. 在第 i 行，a 代表要攻克第 i 個(gè)城堡必須先攻克第 a 個(gè)城堡，如果 a = 0 則代表可以直接攻克第 i 個(gè)城堡。b 代表第 i 個(gè)城堡的寶物數(shù)量, b >= 0。當(dāng)N = 0, M = 0輸入結(jié)束。

Output

對(duì)于每個(gè)測(cè)試實(shí)例，輸出一個(gè)整數(shù)，代表ACboy攻克M個(gè)城堡所獲得的最多寶物的數(shù)量。

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

解題報(bào)告：

? ?建圖很方便，用零號(hào)頂點(diǎn)代表一個(gè)權(quán)值為0的城堡。然后跑的時(shí)候從零號(hào)頂點(diǎn)開始跑m+1個(gè)城堡就好了。比較容易可以看出來(lái)，這個(gè)問(wèn)題是可以優(yōu)化空間和時(shí)間復(fù)雜度的。但是因?yàn)椴豢▋?nèi)存所以不需要做過(guò)多處理。（實(shí)際上，空間只用到了孩子和父親兩個(gè)的關(guān)系，所以可以01滾動(dòng)數(shù)組優(yōu)化掉一維，對(duì)于空間，因?yàn)槭乔笞畲笾祮?wèn)題，可以用線段樹來(lái)優(yōu)化第二維枚舉。）

這題屬于依賴背包，其實(shí)是三維的狀態(tài)。

這里主要是想說(shuō)一下和01背包的區(qū)別，之所以01背包是N^2級(jí)別的復(fù)雜度，這個(gè)是N^3，就是因?yàn)閷?duì)于每一個(gè)根節(jié)點(diǎn)更新狀態(tài)的時(shí)候，孩子節(jié)點(diǎn)不唯一，換句話說(shuō)，01背包中，一個(gè)物品就代表選和不選兩個(gè)決策，他就只有一個(gè)物品；但是放到樹中，這一個(gè)孩子節(jié)點(diǎn)代表的是一棵子樹，所以要枚舉這子樹中選了多少?zèng)]選多少來(lái)更新狀態(tài)， 所以多了一個(gè)量級(jí)的復(fù)雜度。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 200 + 5; vector<int> vv[MAX]; int val[MAX]; int n,m; int dp[MAX][MAX]; void dfs(int cur) {dp[cur][1] = val[cur];int up = vv[cur].size();for(int i = 0; i<up; i++) {int v = vv[cur][i];dfs(v);for(int j = m+1; j>=1; j--) {//j到2也可以ACfor(int k = 1; k<j; k++) {dp[cur][j] = max(dp[cur][j],dp[cur][j-k] + dp[v][k]);}}} } int main() {while(~scanf("%d%d",&n,&m) && n && m) {for(int i = 0; i<=n; i++) vv[i].clear();memset(dp,0,sizeof dp);for(int pre,i = 1; i<=n; i++) {scanf("%d%d",&pre,val+i);vv[pre].pb(i);}dfs(0);printf("%d\n",dp[0][m+1]);}return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【HDU - 1561】The more, The Better（树形背包，dp，依赖背包问题与空间优化，tricks）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。