hdoj1520（入门树形dp）

r囧r小猫 2021-10-26 12:28 289阅读 0赞

题目链接：https://vjudge.net/problem/HDU-1520

题意：和luogu那道没有上司的舞会一样的题，给定一棵带点权的树，父结点和子结点不能同时选，问怎么选使得权值和最大，求最大值即可。

思路：最近开始肝树形dp，从入门题开始QAQ，加油！

用dp\[u\]\[0\]表示结点u不选，dp\[u\]\[1\]表示选，vi是结点u的子结点，那么：

dp\[u\]\[0\]=sum(max(dp\[vi\]\[0\],dp\[vi\]\[1\]))

dp\[u\]\[1\]=val\[u\]+sum(dp\[vi\]\[0\])

一次dfs就ok了，结果为max(dp\[root\]\[0\],dp\[root\]\[1\])，root要自己找。

AC代码：

#include<cstdio>
    #include<algorithm>
    using namespace std;
    
    const int maxn=6005;
    int n,cnt,head[maxn],val[maxn],indeg[maxn],dp[maxn][2];
    struct node{
        int v,nex;
    }edge[maxn];
    
    void adde(int u,int v){
        edge[++cnt].v=v;
        edge[cnt].nex=head[u];
        head[u]=cnt;
    }
    
    void dfs(int u){
        dp[u][1]=val[u];
        for(int i=head[u];i;i=edge[i].nex){
            int v=edge[i].v;
            dfs(v);
            dp[u][0]+=max(dp[v][0],dp[v][1]);
            dp[u][1]+=dp[v][0];
        }
    }
    
    int main(){
        while(~scanf("%d",&n)){
            cnt=0;
            for(int i=1;i<=n;++i){
                scanf("%d",&val[i]);
                head[i]=0,indeg[i]=0,dp[i][0]=0;
            }
            int a,b;
            while(scanf("%d%d",&a,&b),a&&b){
                indeg[a]=1;
                adde(b,a);
            }
            int root;
            for(int i=1;i<=n;++i)
                if(!indeg[i]){
                    root=i;
                    break;
                }
            dfs(root);
            printf("%d\n",max(dp[root][0],dp[root][1]));
        }
        return 0;
    }

转载于:https://www.cnblogs.com/FrankChen831X/p/11372594.html

发表评论取消回复

表情：

评论列表（有 0 条评论，289人围观）

还没有评论，来说两句吧...

相关阅读

相关树形dp1

没有上司的舞会，树形dp include<bits/stdc++.h> define mms(a) memset(a,-1,sizeof(a)) u

超、凢脫俗/ 2023年08月17日 16:36/ 0 赞/ 119 阅读

相关 hdoj 4863 Centroid of a Tree【树的重心+树形dp+数据结构】

题目：[hdoj 4863 Centroid of a Tree][] 来源：[2014 Multi-University Training Contest 1][

墨蓝/ 2022年09月21日 01:04/ 0 赞/ 167 阅读

相关 hdoj1561The more, The Better（树形dp，依赖背包）

题目：[hdoj1561The more, The Better][hdoj1561The more_ The Better] 题意：ACboy很喜欢玩一种战略游戏

客官°小女子只卖身不卖艺/ 2022年09月20日 15:25/ 0 赞/ 161 阅读

相关树形dp入门之poj 2342

题目：[poj2342Anniversary party][poj2342_Anniversary party] 题意：话说一个公司的一些然要去参加一个party，

向右看齐/ 2022年08月23日 11:53/ 0 赞/ 149 阅读

相关 poj2342 树形dp入门

题意：公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在晚会中见到他的直接上司，现在已知每个人的活跃指数和上司关系，求邀请哪些人来能使得晚会的总

心已赠人/ 2022年08月20日 16:06/ 0 赞/ 260 阅读

相关【hdoj2571】命运（dp）

命运 Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64u Submit [Status

妖狐艹你老母/ 2022年07月15日 23:23/ 0 赞/ 137 阅读

相关浅谈树形dp

总结：这一周重点训练了树形dp。对树形dp也有了一定的认识。先说一下总的观点吧。树形dp一般无非就是求出子节点的状态从而进一步去更新根节点的状态。一般的话，

系统管理员/ 2022年02月09日 10:53/ 0 赞/ 334 阅读

相关 hdoj3709（数位dp）

题目链接：https://vjudge.net/problem/HDU-3709 题意：求出\[l,r\]中的平衡数，平衡数即存在一个中心点使得两边的力矩和相等。思路：首

桃扇骨/ 2021年12月21日 01:07/ 0 赞/ 299 阅读

相关偷天换日（树形DP）

[洛谷][Link 1] 比较喜欢(≧∇≦)ﾉ这个建图对于叶子节点，直接处理出f\[i\]\[j\]当前i号节点分j个时间 include<bits/stdc

Dear 丶/ 2021年11月09日 08:04/ 0 赞/ 296 阅读

相关 hdoj1520（入门树形dp）

题目链接：https://vjudge.net/problem/HDU-1520 题意：和luogu那道没有上司的舞会一样的题，给定一棵带点权的树，父结点和子结点不能同时选，

r囧r小猫/ 2021年10月26日 12:28/ 0 赞/ 290 阅读