HDU1561 The more, The Better

Time Limit: 6000/2000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 8490????Accepted Submission(s): 4964

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

?

?

Recommend

LL???|???We have carefully selected several similar problems for you:??1011?2159?2639?1203?2602?

?

分析：

典型的樹形dp的題目。

首先，限制條件是選擇m個物品，而每個物品最多選一次，跟0-1背包的區別在于有依賴關系，那么這層依賴關系我們可以借助于一個樹來解決。借助dfs，從根節點開始dfs，然后直到葉子節點，回朔的時候進行0-1背包dp。

dp[i][j]表示以i為根節點取j個節點（包括根）的最優值
map[i][j]表示i號節點的第j個孩子是什么		?	?
num[i]表示i號節點的孩子數	?	?	?
vis[i]==0表示i號節點沒有被訪問		?	?
?	?	?	?

?

dp[i][j]=max(dp[i][j],dp[i][k]+dp[i的某個孩子節點][j-k])

表示在父親節點i中選k個點和在i的某個孩子中選j-k個點

我們可以知道dp[i][1]=val[i]，因為選一個點的話必須選自己 = =

依賴關系形成森林，要先把樹轉換成森林才能進行樹形DP

增加一個根節點0即可

答案即為dp[0][m+1]：因為增加了一個根節點

?

?

?

1 #include<stdio.h> 2 #include<string.h> 3 int n,m; 4 int num[250]; 5 int map[250][250]; 6 int dp[250][250]; 7 bool vis[250]; 8 int max(int a,int b){ 9 return a>b?a:b; 10 } 11 void dfs(int p) 12 { 13 int i,j,k; 14 //將p的訪問置為true 15 vis[p]=true; 16 //遍歷p的所有孩子 17 for(i=1;i<=num[p];i++) 18 { 19 //t是節點p的第i個孩子 20 int t=map[p][i]; 21 //如果t沒被訪問，dfs它 22 if(!vis[t]) dfs(t); 23 //m反向過來是保證后面的數據不影響前面的，比如當m=5時，j=m，k=2時，等式右邊出現過一次dp[p][2] 24 //而當m=5時，j=2，k=2時， 狀態轉移方程等式左邊出現了dp[p][2]，顯然，這個出現的dp[p][2]不能影響右邊那個dp[p][2] 25 for(j=m;j>=2;j--)//選擇1個的狀態不用更新了，就是節點本身，初始化中已經做了 26 { 27 for(k=1;k<j;k++)//k表示父親需要取的點的個數，j-k表示孩子需要取的點的個數 28 { 29 //如果有值 30 if(dp[t][j-k]!=-1&&dp[p][k]!=-1) 31 dp[p][j]=max(dp[p][j],dp[p][k]+dp[t][j-k]); 32 } 33 } 34 } 35 } 36 int main() 37 { 38 int i,j; 39 while(scanf("%d%d",&n,&m),n||m) 40 { 41 int a,b; 42 dp[0][1]=0; 43 memset(num,0,sizeof(num)); 44 for(i=1;i<=n;i++){ 45 scanf("%d%d",&a,&b); 46 //初始化 47 dp[i][1]=b; 48 map[a][++num[a]]=i; 49 } 50 m++;//增加一個點，森林轉換成樹 51 //初始化 52 for(i=0;i<=n;i++){ 53 dp[i][0]=0;vis[i]=0; 54 for(j=2;j<=m;j++){ 55 dp[i][j]=-1; 56 } 57 } 58 dfs(0); 59 printf("%d\n",dp[0][m]); 60 } 61 return 0; 62 }

?

?

沒過的代碼：

錯誤：第30行的g[a][++num[a]]=i;這里寫成了g[a][++num[i]]=i;?

1 #include <bits/stdc++.h> 2 const int N=2e2+10; 3 using namespace std; 4 int dp[N][N],m,n; 5 int num[N],g[N][N]; 6 bool vis[N]; 7 8 void dfs(int r){ 9 vis[r]=true; 10 for(int i=1;i<=num[r];i++){ 11 int v=g[r][i]; 12 if(!vis[v]) dfs(v); 13 for(int j=m;j>=2;j--){ 14 for(int k=1;k<j;k++){ 15 //這里可以判斷一下如果有值的話 16 if(dp[r][k]!=-1&&dp[v][j-k]!=-1) 17 dp[r][j]=max(dp[r][j],dp[r][k]+dp[v][j-k]); 18 } 19 } 20 } 21 } 22 23 int main(){ 24 freopen("in.txt","r",stdin); 25 memset(dp,-1,sizeof(dp)); 26 while(scanf("%d %d",&n,&m),n||m){ 27 for(int i=1;i<=n;i++){ 28 int a,w; 29 cin>>a>>w; 30 g[a][++num[a]]=i;//存孩子 //這里寫成了g[a][++num[i]]=i; 31 dp[i][1]=w; 32 dp[i][0]=0; 33 } 34 dp[0][1]=0; 35 dp[0][0]=0; 36 m++; 37 dfs(0); 38 cout<<dp[0][m]<<endl; 39 } 40 41 42 return 0; 43 }

?

轉載于:https://www.cnblogs.com/Renyi-Fan/p/7430988.html

總結

以上是生活随笔為你收集整理的HDU1561 The more, The Better的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。