POJ 2342 (树形DP)

时间：2021-06-09 14:57:50

题目链接: http://poj.org/problem?id=2342

题目大意：直属上司和下属出席聚会。下属的上司出现了，下属就不能参加，反之下属参加。注意上司只是指直属的上司。每个人出席的人都有一个快乐值，问最大的快乐值是多少。

解题思路：

首先确定一下顶头上司是谁。

f[v]=u表示u是v的父亲，这样addedge完了之后，从1开始while（f[root]) root=f[root]，最后root就是顶头上司，也就是dfs的起点了。

用dp[i][0]表示对于第i个人不出席的最大快乐值，用dp[i][1]表示出席的最大快乐值。

则dp[i][0]=dp[i][0]+max(dp[son][0],dp[son][1]) ,原因是上司不出席，下属可出席也可不出席，取个大的。

dp[i][1]=dp[i][1]+dp[son][0]，原因是上司一旦出席，下属绝对不能出席。

其中dp[i][1]的初始值为这个人的快乐值。

则ans=max(dp[root][0],dp[root][1])

注意本题的dfs只是起到推进树结构作用，推完树结构之后，还是传统的DP转移方式，不是记忆化搜索。

#include "cstdio"

#include "vector"

#include "cstring"

using namespace std;

#define maxn 6005

int hap[maxn],f[maxn],dp[maxn][],head[maxn],tol;

struct Edge

{

    int to,next;

}e[maxn];

void addedge(int u,int v)

{

    e[tol].to=v;

    e[tol].next=head[u];

    head[u]=tol++;

}

void dfs(int root)

{

    dp[root][]=hap[root];

    for(int i=head[root];i!=-;i=e[i].next) dfs(e[i].to);

    for(int i=head[root];i!=-;i=e[i].next)

    {

        dp[root][]+=max(dp[e[i].to][],dp[e[i].to][]);

        dp[root][]+=dp[e[i].to][];

    }

}

int main()

{

    //freopen("in.txt","r",stdin);

    int n,u,v;

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

    {

        memset(f,,sizeof(f));

        memset(dp,,sizeof(dp));

        memset(head,-,sizeof(head));

        for(int i=; i<=n; i++) scanf("%d",&hap[i]);

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

        {

            scanf("%d%d",&v,&u);

            if(u==&&v==) break;

            f[v]=u;

            addedge(u,v);

        }

        int root=;tol=;

        while(f[root]) root=f[root];

        dfs(root);

        int res=max(dp[root][],dp[root][]);

        printf("%d\n",res);

    }

}
13547096 neopenx 2342 Accepted 408K 0MS C++ 1182B 2014-10-20 12:18:43

相关文章