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