Anniversary party（hdu1520）（poj2342）题解

原题地址：http://poj.org/problem?id=2342

题目大意：

　　上司和下属不能同时参加派对，求参加派对的最大活跃值。

　　关系满足一棵树，每个人都有自己的活跃值（-128~127）

　　求最大的活跃度。

树形DP入门题。

首先讲解一下树形DP，顾名思义，树形DP一定是在树上的DP，与普通的DP相似，具有两个方向。

1.根---->叶

2.叶---->根

其中第二种最为常用。实现方法：从根节点开始DFS（深度优先搜索），一直搜索到叶节点，然后根据其特殊性质赋值。通过回溯更新到根节点。得出答案。

回过来说这道题。

首先是状态。

这道题的DP状态共两维，第一维表示自己本身编号，第二维表示去或者不去。

即dp[i][j] j的取值为0或1,1表示去，0表示不去。

最后的答案即为根节点的状态max(dp[root][0],dp[root][1]);

首先常规操作，建边，找根节点。有向图，我们可以通过统计入度和出度来判断根节点和叶节点。

接下来是状态转移方程：

dp[x][1]+=dp[to][0];
dp[x][0]+=max(dp[to][0],dp[to][1]);

很好理解，x是上司，to是下属，通过下属来更新上司。

一个上司可能有多个下属，但是这些下属只能有一个上司，符合树的定义。

如果这个上司去，那么下属只能不去，所以要加上所有的下属不去的状态。即dp[to][0]

如果上司不去，这个时候需要比较下属去或者不去的大小。

有的同学可能会问了，为什么不直接让下属去多好啊，一步贪心，相当于把树进行了黑白染色，要么黑的去，要么白的去，比较一下大小不就好了？

我刚开始纠结了半天，后来发现了题中所给的条件。

关系满足一棵树，每个人都有自己的活跃值（-128~127）。

由于有些员工过于矫情，去派对自己还不活跃，所以之前的贪心是错误的。

之后比较老总（根节点）去或者不去的大小，选择较大值。

上代码：

#include<cstdio>

#include<algorithm>

using namespace std;

int val[];

int indegree[];

int outdegree[];

struct edge

{

    int to;

    int nxt;

}eg[];

int head[];

int cnt = ;

void add(int x,int y)

{

    eg[cnt].to = y;

    eg[cnt].nxt = head[x];

    head[x] = cnt++;

}

int dp[][];

void dfs(int x)

{

    if(outdegree[x]==)

    {

        dp[x][] = val[x];

        return ;

    }

    for(int i = head[x];i;i=eg[i].nxt)

    {

        int to = eg[i].to;

        dfs(to);

        dp[x][]+=dp[to][];

        dp[x][]+=max(dp[to][],dp[to][]);

    }

}

int main()

{

    int n;

    scanf("%d",&n);

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

    {

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

        dp[i][] = val[i];

    }

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

    {

        int x,y;

        scanf("%d%d",&x,&y);

        if(x==&&y==)

        {

            break;

        }

        indegree[x]++;

        outdegree[y]++;

        add(y,x);

    }

    int root;

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

    {

        if(indegree[i]==)

        {

            root = i;

        }

    }

    dfs(root);

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

}

巴特西

Anniversary party（hdu1520）（poj2342）题解

最新文章

热门文章