樹(shù)形dp 

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

創(chuàng)新互聯(lián)建站專注于?？谄髽I(yè)網(wǎng)站建設(shè),響應(yīng)式網(wǎng)站開(kāi)發(fā),商城網(wǎng)站制作。海口網(wǎng)站建設(shè)公司,為?？诘鹊貐^(qū)提供建站服務(wù)。全流程按需開(kāi)發(fā)網(wǎng)站，專業(yè)設(shè)計(jì)，全程項(xiàng)目跟蹤，創(chuàng)新互聯(lián)建站專業(yè)和態(tài)度為您提供的服務(wù)

f[i][j] 代表以i為根節(jié)點(diǎn) 不包含根節(jié)點(diǎn) 的 j個(gè)城堡

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)略游戲，在一個(gè)地圖上，有N座城堡，每座城堡都有一定的寶物，在每次游戲中ACboy允許攻克M個(gè)城堡并獲得里面的寶物。但由于地理位置原因，有些城堡不能直接攻克，要攻克這些城堡必須先攻克其他某一個(gè)特定的城堡。你能幫ACboy算出要獲得盡量多的寶物應(yīng)該攻克哪M個(gè)城堡嗎？
Input
每個(gè)測(cè)試實(shí)例首先包括2個(gè)整數(shù)，N,M.(1 <= M <= N <= 200);在接下來(lái)的N行里，每行包括2個(gè)整數(shù)，a,b. 在第 i 行，a 代表要攻克第 i 個(gè)城堡必須先攻克第 a 個(gè)城堡，如果 a = 0 則代表可以直接攻克第 i 個(gè)城堡。b 代表第 i 個(gè)城堡的寶物數(shù)量, b >= 0。當(dāng)N = 0, M = 0輸入結(jié)束。
Output
對(duì)于每個(gè)測(cè)試實(shí)例，輸出一個(gè)整數(shù)，代表ACboy攻克M個(gè)城堡所獲得的最多寶物的數(shù)量。
Sample Input
3 20 10 20 37 42 20 10 42 17 17 62 20 0
Sample Output
513

#include 
#include
#include

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]沒(méi)處理前為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)頁(yè)名稱：Themore,TheBetter樹(shù)形dp-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)地址：http://weahome.cn/article/jijsg.html