程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu 1561 樹形dp

hdu 1561 樹形dp

編輯:C++入門知識

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 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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved