HDU 1561 The more, The Better（树形dp之树形01背包）

时间：2024-07-08 10:07:26

传送门：

http://acm.hdu.edu.cn/showproblem.php?pid=1561

The more, The Better

Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 9590    Accepted Submission(s): 5568

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
Source
Recommend
LL
分析：
01背景的基础+树形操作
code：
#include <iostream>

#include<algorithm>

#include <cstdio>

#include<cstring>

using namespace std;

#define max_v 205

struct node

{

    int pa,son,next;

}tree[max_v];

int vis[max_v];

int dp[max_v][max_v];

int ans[max_v][max_v];

int List[max_v];

int value[max_v];

int len,n,m;

void add(int pa,int son)

{

    tree[len].pa=pa;

    tree[len].son=son;

    tree[len].next=List[pa];

    List[pa]=len++;

}

void dfs(int root)

{

    vis[root]=;

    int now=List[root];

    int temp;

    while(now!=-)

    {

        temp=tree[now].son;

        if(!vis[temp])

        {

            dfs(temp);

            for(int k=m;k>=;k--)//01背包

            {

                for(int j=;j<=k;j++)

                {

                    ans[root][k]=max(ans[root][k],ans[root][k-j]+dp[temp][j]);

                }

            }

        }

        now=tree[now].next;

    }

    for(int j=;j<=m+;j++)

    {

        dp[root][j]=ans[root][j-]+value[root];

    }

}

int main()

{

    int a,b;

    while(~scanf("%d %d",&n,&m))

    {

        if(n+m==)

            break;

        len=;

        memset(List,-,sizeof(List));

        for(int i=;i<=n;i++)

        {

            scanf("%d %d",&a,&b);

            value[i]=b;

            add(a,i);

        }

        value[]=;

        memset(vis,,sizeof(vis));

        memset(dp,,sizeof(dp));

        memset(ans,,sizeof(ans));

        dfs();

        printf("%d\n",dp[][m+]);

    }

    return ;

}

相关文章