首页 > 其他 > 详细

hdu 1561 The more, The Better 树形dp

时间:2017-07-23 12:11:21      阅读:251      评论:0      收藏:0      [点我收藏+]

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

做树形dp比较小。

先上网学习下,总结下套路。

dp[i][j]表示在第i个节点,有j个名额选的时候的最大ans,

初始值dp[i][1---tot] = val[i],也就是每一个节点,有1、2、3、。。tot个选择的时候,最大值是自己

然后dfs,回溯的时候,对于每一个儿子,都可以用来更新爸爸,枚举爸爸选了j个,j >= 1因为只有爸爸选了,儿子才能选。

分配给当前回溯的儿子v选了j - k个,其中   1 <= k <= j,还有一部分是k,是爸爸保留的名额。

dp[cur][j] = max(dp[cur][j],   dp[cur][k] + dp[v][j - k]); // j - k可能等于0,也就是不选儿子。

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;

const int maxn = 200 + 20;
struct Edge {
    int u, v, tonext;
}e[maxn * 2];
int num, first[maxn];
void addEdge(int u, int v) {
    e[num].u = u, e[num].v = v, e[num].tonext = first[u];
    first[u] = num++;
}
struct Node {
    int cost, val;
}a[maxn];
int tot, n;
int dp[maxn][maxn];
void dfs(int cur) {
    for (int i = first[cur]; ~i; i = e[i].tonext) {
        int v = e[i].v;
        dfs(v);
        for (int j = tot; j >= 1; --j) { // 当前这个爸爸最多有j个选
            for (int k = 1; k <= j; ++k) { //更新状态,j - k表示留j - k个名额给儿子v选
                dp[cur][j] = max(dp[cur][j], dp[cur][k] + dp[v][j - k]);
            } //其中j不能等于0, 因为爸爸至少要选1个才能选儿子
        }
    }
}
void work() {
    memset(dp, 0, sizeof dp);
    num = 0;
    memset(first, -1, sizeof first);
    tot++;
    for (int i = 1; i <= n; ++i) {
        int per, val;
        cin >> per >> val;
        a[i].val = val;
        addEdge(per, i);
        for (int j = 1; j <= tot; ++j) {
            dp[i][j] = val;
        }
    }
    dfs(0);
    printf("%d\n", dp[0][tot]);
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    while (cin >> n >> tot && (tot + n)) work();
    return 0;
}

 

hdu 1561 The more, The Better 树形dp

原文:http://www.cnblogs.com/liuweimingcprogram/p/7224043.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!