题目描述

你要组织一个由你公司的人参加的聚会。你希望聚会非常愉快,尽可能多地找些有趣的热闹。但是劝你不要同时邀请某个人和他的上司,因为这可能带来争吵。给定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 ;
}

最新文章

  1. SOA服务设计与实现的几个语言无关的原则速记
  2. adb logcat 基本用法
  3. 【转】CentOS下载版本介绍
  4. sublime ctags
  5. ExtJs弹出窗口
  6. linux 下部署 kafka
  7. Git一些其它的功能
  8. angular 实现自定义样式下拉菜单
  9. Python环境以及编辑器
  10. Maven多项目继承:dependencyManagement scope=import
  11. Python单元测试框架 unittest详解
  12. 王之泰201771010131《面向对象程序设计(java)》第二周学习总结
  13. webpack系统配置
  14. 2018牛客网暑期ACM多校训练营(第一场) J - Different Integers - [莫队算法]
  15. 快速切题 usaco ariprog
  16. Python实践练习:选择性拷贝
  17. Codeforces Round #348 (VK Cup 2016 Round 2, Div. 2 Edition) B. Little Artem and Grasshopper 模拟题
  18. pandas数据对齐
  19. Solr6.6.0 用 SimplePostTool索引文件 中文乱码
  20. POJ 2441 Arrange the Bulls(状态压缩DP)

热门文章

  1. Struts第一个程序。
  2. mysql图形化管理工具workbench下载安装以及基本使用
  3. fedora下编译运行java傻瓜入门级教程
  4. Python基础教程(020)--集成开发环境IDE简介--Pycharm
  5. 实验1 C语言环境使用和数据类型 运算符 表达式
  6. LOJ 2541 「PKUWC2018」猎人杀——思路+概率+容斥+分治
  7. 浅谈 STM32 硬件I2C的使用 (中断方式 无DMA 无最高优先级)(转)
  8. JavaScript-Tool-截取头像:ShearPhoto
  9. laravel 中url使用
  10. Note1