hdoj1520（入门树形dp）

题目链接：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=;

int n,cnt,head[maxn],val[maxn],indeg[maxn],dp[maxn][];

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][]=val[u];

    for(int i=head[u];i;i=edge[i].nex){

        int v=edge[i].v;

        dfs(v);

        dp[u][]+=max(dp[v][],dp[v][]);

        dp[u][]+=dp[v][];

    }

}

int main(){

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

        cnt=;

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

            scanf("%d",&val[i]);

            head[i]=,indeg[i]=,dp[i][]=;

        }

        int a,b;

        while(scanf("%d%d",&a,&b),a&&b){

            indeg[a]=;

            adde(b,a);

        }

        int root;

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

            if(!indeg[i]){

                root=i;

                break;

            }

        dfs(root);

        printf("%d\n",max(dp[root][],dp[root][]));

    }

    return ;

}

巴特西

hdoj1520（入门树形dp）

最新文章

热门文章