AcWing1077-cnblog

问题背景
给定一个树形结构的图,每个节点代表一个地点,每个节点有一个守卫的代价。我们希望以最低的代价在树的节点上放置守卫,使得整棵树的所有节点都被监控。可以通过三种方式覆盖一个节点:
- 由父节点监控。
- 由子节点监控。
- 自己放置一个守卫监控自己。
状态表示
定义 $ f[i][k] $ 为第 $ i $ 个节点在状态 $ k $ 下的最小代价,其中状态 $ k $ 有三种取值:
- $ f(i, 0) $:第 $ i $ 号节点由父节点的守卫监控的方案数。
- $ f(i, 1) $:第 $ i $ 号节点由子节点的守卫监控的方案数。
- $ f(i, 2) $:第 $ i $ 号节点自己放置守卫监控自己的方案数。
状态转移方程
根据题意和约束条件,通过递归计算以下三种状态的最小代价:
-
父节点监控 $ f(i, 0) $:节点 $ i $ 被父节点监控,则每个子节点 $ j $ 要么自己监控自己(状态 $ f(j, 2) $),要么被它的子节点监控(状态 $ f(j, 1) $)。
f ( i , 0 ) = ∑ min ( f ( j , 1 ) , f ( j , 2 ) ) f(i, 0) = \sum \min(f(j,1), f(j,2)) f(i,0)=∑min(f(j,1),f(j,2)) -
子节点监控 $ f(i, 1) $:节点 $ i $ 被一个子节点监控。我们要枚举是哪一个子节点 $ k $ 来监控 $ i $,然后在所有方案中取最小值。
f ( i , 1 ) = min k { f ( i , 0 ) + f ( k , 2 ) − min ( f ( k , 1 ) , f ( k , 2 ) ) } f(i, 1) = \min_{k} \{ f(i, 0) + f(k, 2) - \min(f(k,1), f(k,2)) \} f(i,1)=kmin{f(i,0)+f(k,2)−min(f(k,1),f(k,2))}
其中, $ f(i, 0) $ 中包含了所有子节点的最小监控代价之和,这里要去除子节点 $ k $ 的原代价,替换成状态 $ f(k, 2) $(即子节点 $ k $ 自己监控自己)。 -
自我监控 $ f(i, 2) $:节点 $ i $ 自己放置守卫,则所有子节点 $ j $ 可以选择任意一种监控方案:由父节点监控、自己监控或由子节点监控。
f ( i , 2 ) = ∑ min ( f ( j , 0 ) , f ( j , 1 ) , f ( j , 2 ) ) + w ( i ) f(i, 2) = \sum \min(f(j,0), f(j,1), f(j,2)) + w(i) f(i,2)=∑min(f(j,0),f(j,1),f(j,2))+w(i)
其中, $ w(i) $ 表示在节点 $ i $ 放置守卫的代价。
算法流程
- 建树:使用邻接表存储树结构,使用
add函数建立节点之间的连接。 - 找到根节点:在输入数据中标记所有有父节点的节点,剩下未标记的节点即为根节点。
- 深度优先搜索 (DFS):从根节点开始递归遍历树,计算每个节点的三种状态的最小代价。
- 结果输出:最终输出根节点的两种监控方案中的最小代价,即
min(f[root][1], f[root][2])。
代码中的核心部分
dfs(int u):递归计算每个节点在三种状态下的最小代价。利用递归遍历树的结构,自底向上地计算各个状态的代价。add(int a, int b):构建树的邻接表表示,用于方便地遍历子节点。- 状态初始化和递推公式的应用:在 DFS 的过程中,不断更新和计算
f[u][0],f[u][1],f[u][2]。
复杂度分析
由于是树形结构的遍历,算法的时间复杂度为 $ O(N) $,其中 $ N $ 是节点数。空间复杂度同样是 $ O(N) $,主要用于存储树的结构和每个节点的三种状态的代价。
总结
-
这个算法有效利用了树的层次结构和动态规划的递推思想,通过状态转移和自底向上的动态规划求解每个节点的最小监控方案。
-
状态设计和转移公式充分考虑了监控的三种情况,通过分解为子问题并合并结果,实现了最优代价的计算。
-
状态设计和转移公式充分考虑了监控的三种情况,通过分解为子问题并合并结果,实现了最优代价的计算。
这段代码是一个典型的树形动态规划问题的解法,适用于解决诸如最小路径覆盖、监控覆盖等类似的树结构上的最小代价问题。
相关文章:
AcWing1077-cnblog
问题背景 给定一个树形结构的图,每个节点代表一个地点,每个节点有一个守卫的代价。我们希望以最低的代价在树的节点上放置守卫,使得整棵树的所有节点都被监控。可以通过三种方式覆盖一个节点: 由父节点监控。由子节点监控。自己…...
五、SpringBoot3实战(1)
一、SpringBoot3介绍 1.1 SpringBoot3简介 SpringBoot版本:3.0.5 https://docs.spring.io/spring-boot/docs/current/reference/html/getting-started.html#getting-started.introducing-spring-boot 到目前为止,你已经学习了多种配置Spring程序的方式…...
练习LabVIEW第三十三题
学习目标: 刚学了LabVIEW,在网上找了些题,练习一下LabVIEW,有不对不好不足的地方欢迎指正! 第三十三题: 用labview编写一个判断素数的程序 开始编写: LabVIEW判断素数,首先要搞…...
如何在服务器端对PDF和图像进行OCR处理
介绍 今天我想和大家分享一个我在研究技术资料时发现的很好玩的东西——Tesseract。这不仅仅是一个普通的库,而是一个用C语言编写的OCR神器,能够识别一大堆不同国家的语言。我一直在寻找能够处理各种文档的工具,而Tesseract就像是给了我一把…...
Windows 下实验视频降噪算法 MeshFlow 详细教程
MeshFlow视频降噪算法 Meshflow 视频降噪算法来自于 2017 年电子科技大学一篇高质量论文。 该论文提出了一个新的运动模型MeshFlow,它是一个空间平滑的稀疏运动场 (spatially smooth sparse motion field),其运动矢量 (motion vectors) 仅在网格顶点 (m…...
Python入门:如何正确的控制Python异步并发量(制并发量的关键技巧与易错点解析)
文章目录 📖 介绍 📖🏡 演示环境 🏡📒 异步并发量控制 📒📝 Python异步并发简介📝 为什么要限制并发量🎈 资源管理🎈 服务稳定性📝 新手容易犯的错误🎈 忽略并发量限制🎈 错误设置并发量📝 设置并发量要注意的事情🎈 了解任务类型🎈 考虑系统资…...
qt QCheckBox详解
QCheckBox 是 Qt 框架中的一个控件,用于创建复选框,允许用户进行选择和取消选择。它通常用于表单、设置界面和任何需要用户选择的场景。 QCheckBox继承自QAbstractButton类,因此继承了按钮的特性。它表示一个复选框,用户可以通过…...
PAT甲级-1041 Be Unique
题目 题目大意 从一组数字中选出第一个唯一出现的数,输出该数。如果没有,则输出None。 思路 哈希的思想,将数值作为索引,对应该数值出现的次数,然后遍历数组即可。 注意第一个数字是指数字的个数,不是数…...
【jvm】如何设置堆内存大小
目录 1. 使用命令行参数设置2. idea中设置3. 注意事项 1. 使用命令行参数设置 1.在Java命令后添加-Xms和-Xmx参数。2.-Xms参数用于设置JVM的初始堆内存大小,等价于-XX:InitialHeapSize。3.-Xmx参数用于设置JVM的最大堆内存大小,等价于-XX:MaxHeapSize。…...
kernel源码分析 do_msgsnd read_msg
笔者分析的源码是v 5.11.22 链接:msg.c - ipc/msg.c - Linux source code v5.11.22 - Bootlin do_msgsnd static long do_msgsnd(int msqid, long mtype, void __user *mtext,size_t msgsz, int msgflg) {struct msg_queue *msq;struct msg_msg *msg;int err;str…...
掌握 CTE 技巧,实现连续日期和月份的 SQL 报表统计
在 SQL 查询中,报表统计往往涉及到特定时间段内的数据汇总,如每日、每月的销售数据等。然而,面对缺少数据的日期或月份,传统 SQL 查询可能会直接跳过这些日期,使得输出的报表在视觉上并不连续。本文将展示如何利用 CTE…...
【表格解决问题】EXCEL行数过多,WPS如何按逐行分别打印多个纸张中
1 问题描述 如图:我的表格行数太多了。打印在一张纸上有点不太好看 2 解决方式 Step01:先选中你需要打印的部分,找到【页面】->【打印区域】->【设置打印区域】 Step02:先选中一行,找到【插入分页符】 Step0…...
Maven讲解从基础到高级配置与实践
一、基础认知 1.1 Maven 的主要作用 Maven 主要是用来管理 Java 项目构建流程的工具,包括以下几个方面: 依赖管理:通过 POM.xml 文件管理项目的外部依赖库,不同版本的依赖包可以通过 Maven 中央仓库自动下载,减少了…...
Vue3组件式父子传值
下面是使用 <script setup> 语法的 Vue 3 组件之间传值的示例。 示例 1:使用 Props 和 Emits 父组件 <template><div><h1>父组件</h1><ChildComponent :message="parentMessage" @reply="handleReply" /><p>…...
网页自动化测试和爬虫:Selenium库入门与进阶
网页自动化测试和爬虫:Selenium库入门与进阶 在现代Web开发和数据分析中,自动化测试和数据采集成为了开发流程中的重要部分。Python 的 Selenium 库是一种强大的工具,不仅用于网页自动化测试,也在网页爬虫中得到了广泛的应用。本…...
Cells 单元
Goto Data Grid 数据网格 Cells 单元 Content Alignment 内容对齐 显示数值的数据网格单元格会将其内容向右对齐。显示其他类型数据的单元格将其内容向左排列。若要更改单元格内容对齐方式,请处理 ColumnView.RowCellDefaultAlignment 事件。 Selection Modes 选…...
2024/11/2 安卓创建首页界面
Gradle 8.7 bin是指Gradle 8.7版本的二进制包,通常以.zip或.tar.gz格式提供。这个二进制包包含了运行Gradle所需的所有文件,用户可以直接下载并解压使用,无需从源代码编译。 首先了解最常用的布局 线性布局(从上到下&#x…...
SpringSession源码分析
默认对常规Session的理解和使用,如何使用Set-Cookie。 Maven库 常见的spring-session-data-redis依赖spring-session-core <dependency><groupId>org.springframework.session</groupId><artifactId>spring-session-core</artifactId&…...
IIC
IIC 目录 IIC BH1750型号的光照传感器 IIC通信协议 iic物理层 IIC软件层协议 -- 那么一主多从,怎么选中与指定的从机通信呢? 从机设备地址 -- 从手册中查看 IIC 写操作 IIC 读操作 硬件IIC和模拟 IIC 使用 模拟 IIC 使用 !&…...
LLM Observability: Azure OpenAI (一)
作者:来自 Elastic Vinay Chandrasekhar•Andres Rodriguez 我们很高兴地宣布 Azure OpenAI 集成现已全面上市,它提供了对 Azure OpenAI 服务性能和使用的全面可观察性!另请参阅本博客的第 2 部分 虽然我们已经提供了对 LLM 环境的可视性一段…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
前端导出带有合并单元格的列表
// 导出async function exportExcel(fileName "共识调整.xlsx") {// 所有数据const exportData await getAllMainData();// 表头内容let fitstTitleList [];const secondTitleList [];allColumns.value.forEach(column > {if (!column.children) {fitstTitleL…...
Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...
Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
使用Matplotlib创建炫酷的3D散点图:数据可视化的新维度
文章目录 基础实现代码代码解析进阶技巧1. 自定义点的大小和颜色2. 添加图例和样式美化3. 真实数据应用示例实用技巧与注意事项完整示例(带样式)应用场景在数据科学和可视化领域,三维图形能为我们提供更丰富的数据洞察。本文将手把手教你如何使用Python的Matplotlib库创建引…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析
Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问(基础概念问题) 1. 请解释Spring框架的核心容器是什么?它在Spring中起到什么作用? Spring框架的核心容器是IoC容器&#…...
MFC 抛体运动模拟:常见问题解决与界面美化
在 MFC 中开发抛体运动模拟程序时,我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点,详细解析原因并提供解决方案,同时兼顾界面美化,让模拟效果更专业、更高效。 问题一:历史轨迹与小球残影残留 现象 小球运动后,历史位置的 “残影”…...
HTML前端开发:JavaScript 获取元素方法详解
作为前端开发者,高效获取 DOM 元素是必备技能。以下是 JS 中核心的获取元素方法,分为两大系列: 一、getElementBy... 系列 传统方法,直接通过 DOM 接口访问,返回动态集合(元素变化会实时更新)。…...
华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)
题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...
