hdu 1561 樹形dp
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
/**
hdu 1561 樹形dp
題目大意：中文題不在贅述
解題思路：加一個根節點0，構成一棵樹。背包，dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);( j:2~m; k:1~j-1 )
*/
#include
#include
#include
#include
using namespace std;
const int maxn=205;
struct note
{
int v,next;
}edge[maxn*2];
int head[maxn],ip;
int n,m,dp[205][205],a[205];
void init()
{
memset(head,-1,sizeof(head));
ip=0;
}
void addedge(int u,int v)
{
edge[ip].v=v,edge[ip].next=head[u],head[u]=ip++;
}
void dfs(int u,int pre)
{
for(int i=1;i<=m;i++)
dp[u][i]=a[u];
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(v==pre)continue;
dfs(v,u);
for(int j=m;j>1;j--)
{
for(int k=1;k
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 Input3 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
