没有上司的舞会 树形DP

没有上司的舞会 树形DP

 

 

题意:有n个职员可以参加舞会,每个职员有一个欢乐值,职员之间就像一颗树,每个父节点都是子节点的上司,同时一个职员不可以他的直接上司一起参加,。现在选一些员工参加舞会,求参加员工的可能最大快乐值。

做法:设f[i][0]表示i代表的子树之下,i职员不参加的最大快乐值,f[i][1]表示i代表的子树之下,i职员参加的最大快乐值。则状态转移方程得

f[i][0]+=max(f[j][1],f[i][0])如果i不参加,那么他的每个儿子j可以选择参加或者不参加,累加每个儿子的较大的值。

f[i][1]+=f[j][0]如果i参加,那么它需要累加它每个儿子不参加时的最大快乐值。

然后就是从顶头上司根节点开始,深度优先遍历即可

#include<bits/stdc++.h>
using namespace std; int f[1005][2]; int val[1005]; vector<int> v[1005]; int ans; int vis[1005]; void dp(int t) { f[t][0]=0; f[t][1]=val[t]; for(int i=0;i<v[t].size();i++) { int y=v[t][i]; dp(y); f[t][0]+=max(f[y][1],f[y][0]); f[t][1]+=f[y][0]; } } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&val[i]); for(int i=1;i<=n-1;i++) { int a,b; scanf("%d%d",&a,&b); v[b].push_back(a); vis[a]=1; } int root; for(int i=1;i<=n;i++) { if(vis[i]==0) { root=i;break; } } dp(root); printf("%d",max(f[root][1],f[root][0])); }

 

转载于:https://www.cnblogs.com/dongdong25800/p/10834719.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/100939.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • JAVA毕业设计_毕业设计外文翻译范例

    JAVA毕业设计_毕业设计外文翻译范例计算机专业毕业设计论文外文文献中英文翻译——java对象1.IntroductionToObjects1.1TheprogressofabstractionAllprogramminglanguagesprovideabstractions.Itcanbearguedthatthecomplexityoftheproblemsyou’reable…

  • 51单片机学习笔记:合并1602和12864液晶排插接口

    51单片机学习笔记:合并1602和12864液晶排插接口 今天成功合并1602和12864液晶排插接口! 码出来分享下 上面这2个图是1602和12864液晶的排插接口,一般的单片机开发板上都会有仔细观察发现他们的插口大多是相同的, 对于第三脚的对比度调节,1602和12864液晶在硬件上是相反的(1602是低电位方向对比度增强,12864是高电位方向对比度增强),但他们接口位置相同,所以一个10K左右的3脚电位器…

    2022年10月20日
  • Origin绘图快速上手指南

    Origin绘图快速上手指南1、创建工程打开origin后,点击菜单栏“文件”,选择“项目另存为”,给项目命名,并存到某个工作路径。2、导入数据然后将excel中的数据(只要数据)选中后复制到Book1中,从第5行开始粘贴。可以在侧面打开“项目管理器”,给表格“Book1”重命名为“曲线数据”。还可以在表格的“长单位”处给每列数据加上标签。3、那么这时可以直接使用Origin的自动绘图功能了。选择A、B、C所有列,然后点击菜单栏的“绘图”,选择一个折线图,双击即可绘图。这样呢就是将两条曲线放到同一张图中了。如果想要自定

  • SqlSessionFactory介绍[通俗易懂]

    SqlSessionFactory介绍[通俗易懂]SqlSessionFactory是MyBatis的关键对象,它是单个数据库映射关系经过编译后的内存镜像。SqlSessionFactory对象的实例可以通过SqlSessionFactoryBuilder对象来获得,而SqlSessionFactoryBuildr则可以从XML配置文件或一个预先定制的Configuration的实例构建出SqlSessionFactory的实例。每一个MyB…

  • 模拟电路与数字电路基础知识点总结

    模拟电路与数字电路基础知识点总结最近模电真的是让人头疼,模电马上就要结课了,而我的只是水平还停留在第一章第一节,总结起来就是老师讲课听不懂,我又不想听,再加上老师又不想把分给我们,所以我慌了,就再csdn上查找了一下有没有大佬对模电只是点进行过总结;世界之大,总有大佬的:废话不多说,直接上链接,赶快去膜拜:模拟电路与数字电路基础知识点总结千万不要挂科啊~!!!!!!!!!1…

  • treeTable v 1.4.2

    treeTable v 1.4.2treeTablev1.4.2简介treeTable是跨浏览器、性能很高的jquery的树表组件,它使用非常简单,只需要引用jquery库和一个js文件,接口也很简单。优点兼容主流浏览器:支持IE6和IE6+,Firefox,chrome,Opera,Safari接口简洁:在普通表格的基础上增加父子关系的自定义标签就可以组件性能高:内部实现了只绑

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号