总结 树形DP P1352 【没有上司的舞会】

2018-03-04 14:44:35


没有上司的舞会 这是一道树形DP的模板题,树形DP的探索从这里开始。

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

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

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

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

#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;
}