洛谷 P1352 没有上司的舞会 题解【树形DP】

作者: wjyyy 分类: DP,,树形DP,解题报告 发布时间: 2018-03-26 16:05

点击量:8

   树形DP入门

 

题目描述

某大学有N个职员,编号为1~N。他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数Ri,但是呢,如果某个职员的上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数。

 

输入输出格式

输入格式:

第一行一个整数N。(1<=N<=6000)

 

接下来N行,第i+1行表示i号职员的快乐指数Ri。(-128<=Ri<=127)

 

接下来N-1行,每行输入一对整数L,K。表示K是L的直接上司。

 

最后一行输入0 0

 

输出格式:

输出最大的快乐指数。

 

输入输出样例

输入样例#1:
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
0 0
输出样例#1:
5

   这是一道树形DP的模板题,树形DP的探索从这里开始。

 

   因为这不是一棵二叉树,所以我们要用链表模拟向量来存图,并用fa数组来存储各个结点的父亲,以直接找到树的根结点。

 

   依据题意,我们用r数组存储快乐程度的最大值,并用f数组存当第i个结点状态为j时快乐程度最大是多少。

 

   同时,因为要快乐程度最大,所以不掺杂负数,这个题选不选负数是无后效性的,所以负数尽可能不选。

 

   当做DP时,通过DFS函数深搜遍历,根据儿子(们)的状态回溯到自己的状态,这样才能从上一步的最优解推下来。树形DP的基础思想就是这样。

 

Code:

#include<cstdio>
#include<cstring>
int max(int x,int y){return x>y?x:y;}
struct node
{
    int data;
    node *next;
    node()
    {
        next=NULL;
    }
};
node head[6005],*tail[6005];
int r[6005],f[6005][2];//f[i][0]表示自己不去,f[i][1]表示自己去
int fa[6005];
void dfs(int x)
{
    node *root=&head[x];
    while(root->next!=NULL)
    {
        root=root->next;
        dfs(root->data);
        f[x][0]+=max(0,f[root->data][1]);
        f[x][1]+=max(0,f[root->data][0]);
    }
    f[x][1]+=max(0,r[x]);
    return ;
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        fa[i]=i;
        head[i].data=i;
        tail[i]=&head[i];
    }
    for(int i=1;i<=n;i++)
        scanf("%d",&r[i]);
    int a,b;
    scanf("%d%d",&a,&b);
    while(a!=0&&b!=0)
    {
        fa[a]=b;
        node *t=new node();
        t->data=a;
        tail[b]->next=t;
        tail[b]=t;
        scanf("%d%d",&a,&b);
    }
    int k=1;
    while(fa[k]!=k)
        k++;
    dfs(k);
    printf("%d\n",max(f[k][1],f[k][0]));
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */