题目描述
你要组织一个由你公司的人参加的聚会。你希望聚会非常愉快，尽可能多地找些有趣的热闹。但是劝你不要同时邀请某个人和他的上司，因为这可能带来争吵。给定N个人(姓名，他幽默的系数，以及他上司的名字)，编程找到能使幽默系数和最大的若干个人。
输入输出格式
输入格式：
第一行一个整数N(N<100)。接下来有N行，每一行描述一个人的信息，信息之间用空格隔开。姓名是长度不超过20的字符串，幽默系数是在0到100之间的整数。
输出格式：
所邀请的人最大的幽默系数和。
输入输出样例
输入样例#1：
5
BART 1 HOMER
HOMER 2 MONTGOMERY
MONTGOMERY 1 NOBODY
LISA 3 HOMER
SMITHERS 4 MONTGOMERY
输出样例#1：
8
这道题是一道树状dp的入门题目，树状dp的基本思想就是从某节点依次向下层递归，其实和经典的数塔问题没什么区别，这个题就是每个人可以有多个下属（每个节点可以有多个儿子）。
然后难点就是当此节点的人参加聚会时和不参加聚会时的情况处理，详细解释已经写到注释里了。
代码如下：
#include <bits/stdc++.h> using namespace std;
#define inf 0x3f3f3f3f
int n,dp[][],value[],son[],vson[][],topnode,ans;
/*
dp[i][0]表示不让第i人参加聚会的最大值，dp[i][1]让第i个人参见聚会的最大值
value[i]表示第i人的幽默系数
son[i]表示第i个人有多少个下属 vson[i][j]表示第i人的第j个下属是谁
topnode 表示整个公司最上层的人，她没有上司
*/
bool vis[][];//记忆化搜索的标记数组
string namee[],upp[];//分别表示第i人的名字和其上司的名字
int dfs(int i,int j)
{
if (vis[i][j])
return dp[i][j];
vis[i][j]=true;
if (i==)
return ;
if (j==)//这个人参加聚会
{
dp[i][j]=value[i];
for (int k=;k<=son[i];++k)
dp[i][j]+=dfs(vson[i][k],);//他的下属都不能参加聚会，在这条件下找最大值
}
else//人不参加聚会
{
for (int k=;k<=son[i];++k)
dp[i][j]+=max(dfs(vson[i][k],),dfs(vson[i][k],));//他的下属可以有参加或者不参加两种情况
}
return dp[i][j];
}
int main()
{ //freopen("de.txt","r",stdin);
scanf("%d",&n);
memset(son,,sizeof son);
memset(dp,,sizeof dp);
memset(vson,,sizeof vson);
memset(vis,false,sizeof vis);
for (int i=;i<=n;++i)
cin>>namee[i]>>value[i]>>upp[i];
for (int i=;i<=n;++i)
{
bool haveUpp=false;//haveupp表示该人是否有上司
for (int j=;j<=n;++j)
{
if (i==j)
continue;
if (namee[j]==upp[i])
{
haveUpp=true;
vson[j][++son[j]]=i;//把上下属关系处理
break;
}
}
if (!haveUpp)
topnode=i;
}
ans=max(dfs(topnode,),dfs(topnode,));//因为最上层的人也有参加不参加两种可能
printf("%d\n",ans);
return ;
}