没有上司的舞会 树形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之单例模式

  • python读取txt文件并画图[通俗易懂]

    1,使用python读取txt文件已知txt文件内容如下:001124394165256361234567请以第一列为x轴,第二列为y轴画图 步骤如下: 1)使用readlines读取文件 2)建立两个空列表X,Y,将第一列的数字放入X,第二列的数字放入Y中 3)以X,Y为轴画图 实现如下…

  • 时间序列预测(四)—— LSTM模型「建议收藏」

    时间序列预测(四)——LSTM模型文章链接(一)数据预处理(二)AR模型(自回归模型)(三)Xgboost模型(四)LSTM模型(五)Prophet模型(自回归模型)模型原理  LSTM(Long-shorttimememory,LSTM)模型,亦即是长段时间模型。LSTM的原理这篇博客讲的十分的清楚,建议英语好的小伙伴直接去看原文,我这里就大致的翻译精简一下。  人类天…

  • pycharm使用技巧及常用快捷键_程序运行快捷键

    pycharm使用技巧及常用快捷键_程序运行快捷键代码运行快捷键序号快捷键作用1ALT+SHIFT+F10选择程序文件并运行代码2ALT+SHIFT+F9选择程序文件并调试代码3SHIFT+F10运行代码4SHIFT+F9调试代码5CTRL+SHIFT+F10运行当前编辑区的程序

  • loadlibrary 失败 java_LoadLibrary失败,错误代码为14001

    loadlibrary 失败 java_LoadLibrary失败,错误代码为14001我正在使用VisualC2008ExpressEdition来创建仅限资源的DLL.我面临的问题是运行在除了我的另一台计算机上使用DLL的应用程序导致LoadLibrary()函数失败,错误代码为14001.在互联网上搜索似乎是运行缺少MicrosoftVisualC2008RedistributablePackage库的应用程序的计算机的依赖性问题.我的第一步是安装最新…

  • 数据结构与算法经典书籍——大话数据结构(带配套源码)

    数据结构与算法经典书籍——大话数据结构(带配套源码)书本下载链接:链接:https://pan.baidu.com/s/1jgVnbBZoLgA8pshpxbapOQ密码:577l配套程序链接:https://pan.baidu.com/s/1HYka42KngWT2el7T0HO7LA密码:i6hw虽说数据结构以美国人MarkAllenWeiss写的《数据结构与算法分析——C语言实现》最好,但是我发现他的书让人很不容易理解,可能我们…

发表回复

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

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