没有上司的舞会(C++,树形DP)
题目描述
某大学有 nnn 个职员,编号为 1…n1\ldots n1…n。
他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。
现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数 rir_iri
但是呢,如果某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。
所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数。
输入格式
输入的第一行是一个整数 nnn。
第 222 到第 (n+1)(n + 1)(n+1) 行,每行一个整数,第 (i+1)(i+1)(i+1) 行的整数表示 iii 号职员的快乐指数 rir_iri。
第 (n+2)(n + 2)(n+2) 到第 2n2n2n 行,每行输入一对整数 l,kl, kl,k,代表 kkk 是 lll 的直接上司。
输出格式
输出一行一个整数代表最大的快乐指数。
样例 #1
样例输入 #1
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5
样例输出 #1
5
提示
数据规模与约定
对于 100%100\%100% 的数据,保证 1≤n≤6×1031\leq n \leq 6 \times 10^31≤n≤6×103,−128≤ri≤127-128 \leq r_i\leq 127−128≤ri≤127,1≤l,k≤n1 \leq l, k \leq n1≤l,k≤n,且给出的关系一定是一棵树。
解题思路:
首先,注意题中说的是“如果某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。”
也就是说间接上司来不来是无所谓的
接下来讲解本题的解题思路
这道题可以算是树形DP的入门级题目了
树形DP,就是在树形结构中采用动态规划
(说了但好像什么都没说)
常规思路就是自顶向下递推,确定叶子节点后,逐级回归更新父节点
那么这道题为什么采用树形DP呢?
首先题目中给出的是一棵树
其次,我们想要知道舞会的最大快乐指数,除了遍历每一种可能外好像别无选择
那么降低时间复杂度就要想到DP,在本题中也就是树形DP
思路很简单,每个职员只有两种状态:来、不来
我们用dp[now][1]
表示来,dp[now][0]
表示不来
那么有
//树形DP
void dfs(int now) {//参加dp[now][1] = happy[now];//参加,初始化为自己的快乐指数//不参加for (int i = head[now]; i != -1; i = edges[i].next) {//遍历子节点int v = edges[i].v;dfs(v);//返回后更新dp[now][0] += max(dp[v][0], dp[v][1]);//不参加,需要累加子节点来的情况dp[now][1] += dp[v][0];//参加,需要累加子节点不来的情况}
}
最后,AC代码如下
#include <iostream>
#include <string.h>
using namespace std;
const int max_n = 6e3;
const int min_r = -128;
const int max_r = 127;int n, u, v;
int happy[max_n + 1];
int in[max_n + 1];
//链式前向星
struct edge { int v, next; }edges[max_n + 1];
int head[max_n + 1];
int tot = -1;
//树形DP
long long dp[max_n + 1][2];//存边
void add_edge(int u, int v) {edges[++tot] = { v,head[u] }; head[u] = tot;
}//树形DP
void dfs(int now) {//参加dp[now][1] = happy[now];//参加,初始化为自己的快乐指数//不参加for (int i = head[now]; i != -1; i = edges[i].next) {//遍历子节点int v = edges[i].v;dfs(v);//返回后更新dp[now][0] += max(dp[v][0], dp[v][1]);//不参加,需要累加子节点来的情况dp[now][1] += dp[v][0];//参加,需要累加子节点不来的情况}
}int main() {memset(head + 1, -1, sizeof(int) * max_n);cin >> n;for (int i = 1; i <= n; i++) cin >> happy[i];for (int i = 1; i < n; i++) {//存图cin >> u >> v;add_edge(v, u);//反向存边,自顶向下in[u]++;}for (int i = 1; i <= n; i++)if (!in[i]) {//从根节点开始dfs(i);cout << max(dp[i][0], dp[i][1]) << endl;break;}return 0;
}
相关文章:

没有上司的舞会(C++,树形DP)
题目描述 某大学有 nnn 个职员,编号为 1…n1\ldots n1…n。 他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。 现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数 ri…...

【java基础】static和final关键字的作用及其用法详解
文章目录static关键字静态字段静态方法静态代码块静态内部类final关键字final字段final方法final类static关键字 这个关键字表示静态的,用于不同地方意思不一样 静态字段 如果我们将其作用到字段上,那么该字段为类所拥有,我们使用new关键字…...

#集成学习#:bagging、boosting、stacking和blending
集成学习是一种机器学习方法,旨在提高单个模型的性能和鲁棒性。它基于这样一个假设:通过结合多个模型的预测结果,可以获得更好的预测性能,因为每个模型都可能从数据中提取不同的信息,因此他们的错误也可能是不同的&…...

NCRE计算机等级考试Python真题(一)
第一套试题1、关于数据的存储结构,以下选项描述正确的是A.数据所占的存储空间量B.数据在计算机中的顺序存储方式C.数据的逻辑结构在计算机中的表示D.存储在外存中的数据正确答案: C2、关于线性链表的描述,以下选项中正确的是A.存储空间不一定…...

C#协变逆变
文章目录协变协变接口的实现逆变里氏替换原则协变 协变概念令人费解,多半是取名或者翻译的锅,其实是很容易理解的。 比如大街上有一只狗,我说大家快看,这有一只动物!这个非常自然,虽然动物并不严格等于狗…...

算法设计与分析期末考试复习(四)
贪心算法(Greedy Algorithm) 找零钱问题 假设有4种硬币,面值分别为:二角五分、一角、五分和一分,现在要找给顾客六角三分钱,如何找使得给出的硬币个数最少? 首先选出1个面值不超过六角三分的最…...

qsort函数排序数据 and 模拟实现qosrt函数(详解)
前言:内容包括使用库函数qsort排序任意类型的数据,模拟实现qsort函数(冒泡排序的逻辑) 我们先了解qsort函数的语法:qsort函数默认按照升序排序数据 void qsort (void* base, size_t num, size_t size,int (*compar)(…...

Mysql视图,存储过程,触发器,函数以及Mysql架构
一,视图视图是基于查询的一个虚拟表 , 也就是将sql语句封装起来, 要用的时候直接调用视图即可, select语句查询的表称为基表, 查询的结果集称为虚拟表, 基本表数据发生了改变, 那么视图也会发生改变, 使用视图就是为了简化查询语句.1.CREATE VIEW view_admin AS SELECT * FROM…...

什么是线程死锁?如何解决死锁问题
死锁,一组互相竞争的资源的线程之间相互等待,导致永久阻塞的现象。 如下图所示: 与死锁对应的,还有活锁,是指线程没有出现阻塞,但是无限循环。 有一个经典的银行转账例子如下: 我们有个账户类…...

C语言几种判断语句简述
C 判断 判断结构要求程序员指定一个或多个要评估或测试的条件,以及条件为真时要执行的语句(必需的)和条件为假时要执行的语句(可选的)。 C 语言把任何非零和非空的值假定为 true,把零或 null 假定为 fals…...

【python学习笔记】:SQL常用脚本(二)
11、四舍五入ROUND函数 ROUND ( numeric_expression , length [ ,function ] ) function 必须为 tinyint、smallint 或 int。 如果省略 function 或其值为 0(默认值),则将舍入 numeric_expression。 如果指定了0以外的值,则将截…...

【Linux】进程地址空间
文章目录🎪 进程地址空间🚀1.写时拷贝与虚拟地址🚀2.地址空间引入🚀3.地址空间的意义⭐3.1 虚拟地址寻址⭐3.2 虚拟地址意义🎪 进程地址空间 地址空间(address space)表示任何一个计算机实体所…...

Qt音视频开发17-vlc内核回调拿图片进行绘制
一、前言 在众多播放器中,支持的种类格式众多,并支持DVD影音光盘,VCD影音光盘及各类流式协议,提供了sdk进行开发,这点是至关重要的,尽管很多优秀的播放器很牛逼,由于没有提供sdk第三方开发&…...

安装配置DHCP
本次实验采用CentOS71.检查在安装DHCP之前先使用rpm命令查看系统中已有的DHCP软件包rpm -qa | grep dhcp由此可知,系统中尚未安装DHCP软件包2.安装我们可以使用yum命令为系统安装DHCP软件包yum -y install dhcp安装完成后再次检查可以看到DHCP软件包3.配置dhcp配置文…...

MarkDown中写UML图的方法
目录序UML图之顺序图顺序图的四个要素关于消息箭头的语法Mermaid中顺序图的简单例子样例用小人表示对象为对象设置别名激活对象UML图之类图类图中常见的关系关于不同类型关系的语法Mermaid中类图的简单例子样例类定义的两种方式为类定义成员双向关系的表示多重性关系的表示UML之…...

Axure8设计—动态仪表盘
本次分享的的案例是Axure8制作的动态仪表盘,根据设置的数值,仪表盘指针旋转到相应的值位置 预览地址:https://2qiuwg.axshare.com 下载地址:https://download.csdn.net/download/weixin_43516258/87502161 一、制作原型 1、首先创建空白页…...

【C++】类和对象的六个默认成员函数
类的6个默认成员函数构造函数概念特性析构函数概念特性拷贝构造函数概念特征拷贝构造函数典型调用场景:赋值运算符重载运算符重载赋值运算符重载取地址及const取地址操作符重载类的6个默认成员函数 到底什么是类的6个默认成员函数呢?相信大家一定对此怀…...

4、算法MATLAB---认识矩阵
认识矩阵1、矩阵定义和基本运算1.1 赋值运算符:1.2 等号运算符:1.3 空矩阵1.4 一行一列矩阵1.5 行矩阵(元素用空格或逗号分隔)1.6 列矩阵(分号表示换行)1.7 m行n列的矩阵:行值用逗号间隔&#x…...

vue3+rust个人博客建站日记2-确定需求
反思 有人说过我们正在临近代码的终结点。很快,代码就会自动产生出来,不需要再人工编写。程序员完全没用了,因为商务人士可以从规约直接生成程序。 扯淡!我们永远抛不掉代码,因为代码呈现了需求的细节。在某些层面上&a…...

Linux安装云原生网关Kong/KongA
目录1 概述2 创建服务器3 安装postgres4 安装kong5 安装node6 安装KONGA1 概述 Kong Kong是一款基于OpenResty(NginxLua模块)编写的高可用、易扩展的开源API网关,专为云原生和云混合架构而建,并针对微服务和分布式架构进行了特别…...

Vue学习笔记(2)
2.1 事件处理 2.1.1 事件监听器 JavaScript:通过获取DOM对象再往DOM对象上使用addEventListener注册监听事件 const btn document.querySelector(#my-button) btn.addEventListener(click, function() {alert(点击事件!) })jQuery:通过$选择器绑定对象…...

2023年三月份图形化四级打卡试题
活动时间 从2023年3月1日至3月21日,每天一道编程题。 本次打卡的规则如下: 小朋友每天利用10~15分钟做一道编程题,遇到问题就来群内讨论,我来给大家答疑。 小朋友做完题目后,截图到朋友圈打卡并把打卡的截图发到活动群…...

Python操作Excel
Python中对Excel文件的操作包括:读、写、修改。如果要对其进行如上的操作需要导入Python的第三方模块:xlrd、xlwd、xlutils,其分别对应Python的读、写、修改的操作 一、安装Python的第三方模块 二、操作Excel的基本步骤 1、导入响对应的模…...

Codeforces Round #853 (Div. 2) C. Serval and Toxel‘s Arrays【统计次数,算贡献】
链接 传送门 分析 这道题想法其实很简单,样例的计算方法一定要看懂。以样例1为例,根据他的操作方法可以得到两个新的数组,和一个原来的数组,总共三个数组。 1 2 3 4 2 3 4 5 3 他们两两配对去重,求出总的value。由于每…...

微信小程序-1:比较两数的大小
程序来源》微信小程序开发教程(第二章) 主编:黄寿孟、易芳、陶延涛 ISBN: 9787566720788 程序运行结果: <!--index.wxml--> <view class"container"> <text>第一个数字:&…...

数据结构——树
深度优先/广度优先遍历深度优先:访问根节点对根节点的 children 挨个进行深度优先遍历const tree {val: "a",children: [{val: "b",children: [{val: "d",children: [],},{val: "e",children: [],},],},{val: "c&quo…...

【华为OD机试模拟题】用 C++ 实现 - 找到它(2023.Q1)
最近更新的博客 【华为OD机试模拟题】用 C++ 实现 - 去重求和(2023.Q1) 文章目录 最近更新的博客使用说明找到它题目输入输出示例一输入输出示例二输入输出说明Code使用说明 参加华为od机试,一定要注意不要完全背诵代码,需要理解之后模仿写出,通过率才会高。 华为 OD …...

python中yield的使用
在 Python 中,yield 是一个关键字,它用于定义生成器函数。生成器函数是一个特殊的函数,可以返回一个迭代器,当生成器函数被调用时,它不会立即执行,而是返回一个生成器对象,通过迭代生成器对象可…...

GO进阶(4) 深入Go的内存管理
Go语言成为高生产力语言的原因之一自己管理内存:Go抛弃了C/C中的开发者管理内存的方式,实现了主动申请与主动释放管理,增加了逃逸分析和GC,将开发者从内存管理中释放出来,让开发者有更多的精力去关注软件设计ÿ…...

【C++】类与对象理解和学习(下)
放在专栏【C知识总结】,会持续更新,期待支持🌹建议先看完【C】类与对象理解和学习(上)【C】类与对象理解和学习(中)本章知识点概括Ⅰ本章知识点概括Ⅱ初始化列表前言在上一篇文章中,…...