hdu 1561 The more, The Better 樹狀DP
來源:程序員人生 發布時間:2015-05-11 08:59:25 閱讀次數:3281次
The more, The Better
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 5844 Accepted Submission(s): 3476
Problem Description
ACboy很喜歡玩1種戰略游戲,在1個地圖上,有N座城堡,每座城堡都有1定的寶物,在每次游戲中ACboy允許攻克M個城堡并取得里面的寶物。但由于地理位置緣由,有些城堡不能直接攻克,要攻克這些城堡必須先攻克其他某1個特定的城堡。你能幫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
對每一個測試實例,輸出1個整數,代表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
Author
8600
Source
HDU 2006⑴2 Programming Contest
鏈接:http://acm.hdu.edu.cn/showproblem.php?pid=1561
做法:設1個0節點,本身價值是0,dp[i][j]表示第i個節點,取了j個節點后的價值。由于先取父親才能取兒子,所以要從dp[i][1] 開始轉移。把子節點的狀態轉移到父親節點。
由于和分組背包1樣,子節點不能重復更新父親節點,所之外層循環父節點狀態,從大到小,內層循環子節點狀態。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <malloc.h>
#include <ctype.h>
#include <math.h>
#include <string>
#include <iostream>
#include <algorithm>
using namespace std;
#include <stack>
#include <queue>
#include <vector>
#include <deque>
#include <set>
#include <map>
#define INF 999999999
#define eps 0.00001
#define LL __int64d
#define pi acos(⑴.0)
vector<int> son[210];
int dp[210][210];
int val[210];
int n,m;
void dfs(int nw)
{
//dp[nw][0]=0;
dp[nw][1]=val[nw];
for(int i=0;i<son[nw].size();i++)
{
dfs(son[nw][i]);
int ss=son[nw][i];
for(int k=m;k>=1;k--)
{
if(dp[nw][k]!=⑴)
{
for(int j=1;j<=m;j++)
{
if(dp[ss][j]==⑴)
break;
dp[nw][j+k]=max(dp[ss][j]+dp[nw][k],dp[nw][j+k]);
}
}
}
}
}
int main()
{
while(scanf("%d%d",&n,&m),n||m)
{
memset(dp,⑴,sizeof dp);
for(int i=0;i<=n;i++)
{
son[i].clear();
}
val[0]=0;
for(int i=1;i<=n;i++)
{
int a,b;
scanf("%d%d",&a,&val[i]);
son[a].push_back(i);
}
dfs(0);
printf("%d
",dp[0][m+1]);
}
return 0;
}
生活不易,碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈