樹形dp 

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

創(chuàng)新互聯(lián)建站專注于海口企業(yè)網(wǎng)站建設,響應式網(wǎng)站開發(fā),商城網(wǎng)站制作。海口網(wǎng)站建設公司,為海口等地區(qū)提供建站服務。全流程按需開發(fā)網(wǎng)站，專業(yè)設計，全程項目跟蹤，創(chuàng)新互聯(lián)建站專業(yè)和態(tài)度為您提供的服務

f[i][j] 代表以i為根節(jié)點 不包含根節(jié)點 的 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很喜歡玩一種戰(zhàn)略游戲，在一個地圖上，有N座城堡，每座城堡都有一定的寶物，在每次游戲中ACboy允許攻克M個城堡并獲得里面的寶物。但由于地理位置原因，有些城堡不能直接攻克，要攻克這些城堡必須先攻克其他某一個特定的城堡。你能幫ACboy算出要獲得盡量多的寶物應該攻克哪M個城堡嗎？
Input
每個測試實例首先包括2個整數(shù)，N,M.(1 <= M <= N <= 200);在接下來的N行里，每行包括2個整數(shù)，a,b. 在第 i 行，a 代表要攻克第 i 個城堡必須先攻克第 a 個城堡，如果 a = 0 則代表可以直接攻克第 i 個城堡。b 代表第 i 個城堡的寶物數(shù)量, b >= 0。當N = 0, M = 0輸入結束。
Output
對于每個測試實例，輸出一個整數(shù)，代表ACboy攻克M個城堡所獲得的最多寶物的數(shù)量。
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;
}

網(wǎng)頁名稱：Themore,TheBetter樹形dp-創(chuàng)新互聯(lián)
文章網(wǎng)址：http://www.chinadenli.net/article36/jijsg.html

成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供營銷型網(wǎng)站建設、網(wǎng)站策劃、品牌網(wǎng)站設計、網(wǎng)站設計、關鍵詞優(yōu)化、品牌網(wǎng)站建設

廣告

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