(luogu1352) 没有上司的舞会

发表于 分类于 ， ，

树型 dp 经典题

思路:

当然是树型 dp

设 d [i][0/1] 为以 i 为根的子树，i 是否参加的最优解

如果 i 参加，则 i 的下属不会参加， 即 d [i][1] 等于 d [son (i)][0] 中和的最大值

如果 i 不参加，则 i 的下属可参加可不参加， 即 d [i][0] 等于 d [son (i)][0/1] 中和的最大值

最终答案为 d [root][1] 与 d [root][0] 中的最大值

具体实现看代码

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <iostream>
#include <cstdio>
using namespace std;
const int Mn(6050),UD(0xc0c0c0c0);  //UD为最小值
inline int _max(int x,int y) { return x>y ? x : y; }
int fa[Mn]; //某职员的上司
int ch[Mn][Mn]; //某职员的下属, ch[i][0]表示其有几个下属
int r[Mn],d[Mn][2]; //某职员参加的快乐指数, dp数组
int f(int x,int isp)    //使用记忆化搜索dp
{
    if(d[x][isp]!=UD)    return d[x][isp]; //如果d[x][isp]已经搜过
    else if(!ch[x][0])
    { return d[x][isp] = r[x]*isp; }    //如果该职员无下属, 直接计算
    else
    {
        int ret(0);
        if(!isp)    //如果该职员不参加
        {
            for(int i(1);i<=ch[x][0];++i)
                if(_max(f(ch[x][i],1),f(ch[x][i],0))>0)    ret += max(d[ch[x][i]][1],d[ch[x][i]][0]);
            return d[x][isp] = ret;
        }
        else    //如果参加
        {
            for(int i(1);i<=ch[x][0];++i)
                if(f(ch[x][i],0)>0)    ret += d[ch[x][i]][0];
            return d[x][isp] = r[x] + ret;
        }
    }
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i(1);i<=n;++i)
        scanf("%d",r+i);
    for(int i(1);i<n;++i)   //读入关系
    {
        int l,k;
        scanf("%d%d",&l,&k);
        fa[l] = k;
        ch[k][++ch[k][0]] = l;
    }
    int rt(1);  //树根
    for(;fa[rt];rt=fa[rt]); //寻找树根
    for(int i(1);i<=n;++i)    d[i][1] = d[i][0] = UD;  //初始化为最小值
    cout << _max(f(rt,1),f(rt,0));
    return 0;
}