HDU1561 - The more, The Better - 树形dp

The more, The Better

题目链接

分类：

dfs and similar

dp

trees

1.题意概述

• ACboy很喜欢玩一种战略游戏，在一个地图上，有N座城堡，每座城堡都有一定的宝物，在每次游戏中ACboy允许攻克M个城堡并获得里面的宝物。但由于地理位置原因，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡。你能帮ACboy算出要获得尽量多的宝物应该攻克哪M个城堡吗？
• 输入：每个测试实例首先包括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输入结束。

2.解题思路

• 我们定义 dp[i][j] 为当前i节点及其子树下最多选择j个城市的最大值，那么对于某个节点 p :
  1. 判断p当前有没有孩子，如果有则继续dfs下去（这就是树形dp的过程），否则进入操作2。
  2. 将 p 的状态更新到父亲p‘上： dp[p‘][i]=max(dp[p‘][j]+dp[p][k]) ，其中 j+k=i,j>0,k>0,2≤i≤bmax
  3. 那么答案就是 dp[0][bmax] ！

3.AC代码

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
#define maxn 10010
#define lson root << 1
#define rson root << 1 | 1
#define lent (t[root].r - t[root].l + 1)
#define lenl (t[lson].r - t[lson].l + 1)
#define lenr (t[rson].r - t[rson].l + 1)
#define N 202
#define eps 1e-6
#define pi acos(-1.0)
#define e exp(1.0)
using namespace std;
const int mod =  + ;
typedef long long ll;
typedef unsigned long long ull;
int head[N], v[N] , dp[N][N], cnt;  // 0上最长，1下次长，2下最长
struct node
{
    int to, next;
} E[N << ];
void init()
{
    memset(head, -, sizeof head);
    memset(dp, , sizeof(dp));
    cnt = ;
}
void addedge(int u, int v)
{
    E[cnt].to = v;
    E[cnt].next = head[u];
    head[u] = cnt++;
}
void dfs(int u, int res)
{
    dp[u][] = v[u];
    if (res == )
        return;
    for (int i = head[u]; i != -; i = E[i].next)
    {
        int v = E[i].to;
        dfs(v, res - );
        for (int j = res; j > ; j--)
            for (int k = ; k < j; k++)
                dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[v][k]);
    }
}
int main()
{
    int n, m;
    while (~scanf("%d%d", &n, &m), n + m)
    {
        init();
        for (int i = ; i <= n; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            addedge(a, i);
            v[i] = b;
        }
        dfs(, m + );
        printf("%d\n", dp[][m + ]);
    }
    return ;
}