聚会的快乐【树形dp】

100 阅读 0 评论 66 点赞

我是靠谱客的博主笑点低老师，这篇文章主要介绍聚会的快乐【树形dp】，现在分享给大家，希望可以做个参考。

题目描述

　　你要组织一个由你公司的人参加的聚会。你希望聚会非常愉快，尽可能多地找些有趣的热闹。但是劝你不要同时邀请某个人和他的上司，因为这可能带来争吵。给定N个人(姓名，他幽默的系数，以及他上司的名字)，编程找到能使幽默系数和最大的若干个人。

输入输出格式

输入格式：

　　第一行一个整数N(N < 100)。接下来有N行，每一行描述一个人的信息，信息之间用空格隔开。姓名是长度不超过20的字符串，幽默系数是在0到100之间的整数。

输出格式：

　　所邀请的人最大的幽默系数和。

解题思路：

这是一到树形动态规划题，用数组d[i][1]表示i去时的最大值，d[i][0]表示i不去时的最大值。当i去时，它的下属不去，则d[i][1]=d[i][1]+d[y][0];当i不去时，它的下属可去可不去（取最大值），则d[i][0]+=max(d[y][0],d[y][1]),其中y为i的下属。递归每一个点即可。

复制代码

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
#include<iostream>
#include<cstdio>
#include<cstring>
#include<map>
using namespace std;
map<string,int>f;
int s[110][110],n,i,j,rood,d[110][2];
struct node
{
    string son,father;
    int m;
}q[110];
void dp(int r)
{
    int y,i1;
    d[r][1]=q[r].m;
    d[r][0]=0;
    for(i1=1;i1<=s[r][0];i1++)
    {
        y=s[r][i1];
        dp(y);
        d[r][1]+=d[y][0];
        d[r][0]+=max(d[y][0],d[y][1]);
    }
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(i=1;i<=n;i++) 
    {
        cin>>q[i].son>>q[i].m>>q[i].father;
        f[q[i].son]=i;
    }
    for(i=1;i<=n;i++)
       s[f[q[i].father]][++s[f[q[i].father]][0]]=i;
    for(i=1;i<=n;i++)
       if(!f[q[i].father])
         rood=i;
    dp(rood);
    cout<<max(d[rood][0],d[rood][1]);
    return 0;
}