xindoo is
always here

hdoj 1520 Anniversary party(树形dp)


题目链接

   按照等级我们可以建一颗树,如图

      我们可以把一个节点当做一个人,每个节点都有一个权重。按照题目意思,如果我们取了某个节点,那么他的父节点和子节点都是不能取的。按要求选取节点,使得选取节点的权重和最大。

     DP,no表示不选择i点时,i点及其子树能选出的最多人数,is表示选择i点时,i点及其子树的权值和最大。

状态转移方程:

—对于叶子节点 dp[k].no = 0, dp[k].no = a[k].v

—对于非叶子节点i,

—dp[i].no = ∑max(dp[j][0], dp[j][1]) (j是i的儿子)

—dp[i].is = v + ∑dp[j].no (j是i的儿子) 

代码:

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <string.h>
using namespace std;

struct node
{
    int v;
    int is, no;
    vector<int> son;
}a[6010];

bool f[6010];

void dp(int x)
{
    int t;
    for (unsigned int i = 0; i < a[x].son.size(); i++)
    {
        t = a[x].son[i];
        dp(t);
        a[x].is += a[t].no;
        a[x].no += max(a[t].no, a[t].is);
    }
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        for (int i = 1; i <= n; i++)
        {
            scanf("%d", &a[i].v);
            a[i].son.clear();
            a[i].is = a[i].v;
            a[i].no = 0;
        }
        int son, fa;
        memset(f, 0, sizeof(f));
        while (scanf("%d %d",&son, &fa) && son+fa)
        {
            a[fa].son.push_back(son);
            f[son] = 1;
        }
        for (int i = 1; i <= n; i++)
        {
            if (f[i] == false)
            {
                dp(i);
                printf("%d\n",max(a[i].is, a[i].no));
                break;
            }
        }
    }
    return 0;
}


打赏
未经允许不得转载:XINDOO » hdoj 1520 Anniversary party(树形dp)
分享到: 更多 (0)

评论 抢沙发

xindoo

联系我联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏