樹形dp 

dp[i][j] 代表以i為根節點 包含根節點的 有j個城堡

創新互聯建站專注于海口企業網站建設,響應式網站開發,商城網站制作。海口網站建設公司,為海口等地區提供建站服務。全流程按需開發網站，專業設計，全程項目跟蹤，創新互聯建站專業和態度為您提供的服務

f[i][j] 代表以i為根節點 不包含根節點 的 j個城堡

View Code

The more, The Better

Time Limit :6000/2000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) :1   Accepted Submission(s) : 1
Font: Times New Roman| Verdana | Georgia
Font Size: ← →
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 20 10 20 37 42 20 10 42 17 17 62 20 0
Sample Output
513

#include <stdio.h>
#include<algorithm>
#include<string.h>

struct node
{
int index ;
    node*next ;
}adj[205];
bool vis[205];
int dp[205][205], f[205][205], w[205], n, m;
void add(int x, int y)
{
    node*p = new node;
    p->index = y;
    p->next = adj[x].next;
    adj[x].next= p;
}
int max(int a, int b)
{return a>=b ?a :b ; }
void dfs(int now)
{
int i;
    vis[now]= 1;
    node*p = adj[now].next;
while( p!=NULL && !vis[p->index] )
    {
        dfs(p->index);

for(i=m; i>=1; i--) // 一定要逆序！ f[i][j]沒處理前為0 for(int j=1; j<=i; j++)
            {
                f[now][i]= max(f[now][i], f[now][i-j] + dp[p->index][j]);
            }
        p= p->next;
    }
for(i=1; i<=m; i++)
        dp[now][i]= f[now][i-1] + w[now];
}
int main()
{
int i, a;
while(scanf("%d %d", &n, &m), m|n)
    {
        memset(dp,0, sizeof(dp));
        memset(f,0, sizeof(f));
        memset(vis,0, sizeof(vis));
for(i=0; i<=n; i++)
        {
            adj[i].next= NULL;
        }
for(i=1; i<=n; i++)
        {
            scanf("%d %d", &a, &w[i]);
            add(a, i);
        }
        dfs(0);
        printf("%d
", f[0][m]);
    }
return 0;
}

網頁名稱：Themore,TheBetter樹形dp-創新互聯
文章網址：http://vcdvsql.cn/article36/jijsg.html

成都網站建設公司_創新互聯，為您提供營銷型網站建設、網站策劃、品牌網站設計、網站設計、關鍵詞優化、品牌網站建設

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯