hdoj1520（入门树形dp）

r囧r小猫 2021-10-26 12:28 322阅读 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 条评论，322人围观）

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

相关阅读

相关树形dp1

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

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

相关树形DP例题

树形DP例题 DP感觉还是有点陌生，但是这个必须要强化，这类题型实在是太常见了 -------------------- 一、[题目链接：hdu 1520：Anni

忘是亡心i/ 2023年06月19日 06:47/ 0 赞/ 40 阅读

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

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

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

相关树形dp入门题，上司的舞会

遍历根节点，当前节点为u，一次遍历儿子节点x 状态转移方程： d p \[ u \] \[ 0 \] + = m a x ( d p \[ x \] \[ 1 \]

川长思鸟来/ 2022年09月03日 13:16/ 0 赞/ 31 阅读

相关树形dp入门之poj 2342

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

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

相关 poj2342 树形dp入门

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

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

相关【hdoj2571】命运（dp）

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

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

相关 hdoj3709（数位dp）

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

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

相关偷天换日（树形DP）

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

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

相关 hdoj1520（入门树形dp）

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

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