题解:P11501 [ROIR 2019] 探险队(Day 2)
前言:这道题 dp 做法找环的部分还没有用拓扑做的,补充一下。
这道题其实很像“上司的舞会”,就是求树上最大独立集。
这里我们把每个人向他讨厌的那个人连边(发现所有点出度均为 1 1 1,所以这是一个基环树)然后求树上相邻两个结点不能同时选择时,最多能选多少个点。
如果是在普通的树上,设 f [ i ] [ 1 / 0 ] f[i][1/0] f[i][1/0] 表示结点 i i i 选或不选的最大价值,dp 即可。
基环树相当于套了一个环,考虑把环上的每一个点都当作根,跑一遍它们子树的最大点独立集(注意不能走到环上的点),然后再用“给一个环,相邻的两个元素不选,求选得的最大总和”的 dp 模板,对“基环”上的点再跑一遍 dp 把答案整合起来即可。
因为 DAG 图具有良好的 dp 结构,找环可以用拓扑排序,先把普通的点都 dp 了,拓扑结束后入度依然不为 0 0 0 的点就是环上的点。
一些实现细节见代码。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 3e5 + 7;
const ll inf = 1e18;int a[maxn], ind[maxn]; // ind记录入度
ll f[maxn][2]; // f[u][1/0]表示以选/不选u,其子树能得到的最大点独立集大小
bool vis[maxn]; // 记录每个点所在的连通块是否访问过int main(){ios::sync_with_stdio(false); cin.tie(0);int n;cin >> n;for(int i = 1; i <= n; i ++){cin >> a[i];if(a[i] != -1){ind[a[i]] ++;}}queue<int> q;for(int i = 1; i <= n; i ++){if(ind[i] == 0){q.push(i);}f[i][1] = 1; // 初始化dp}ll ans = 0;while(!q.empty()){int u = q.front(); q.pop();int v = a[u];if(v == -1){ans += max(f[u][0], f[u][1]); // 说明这个根节点不在环上,那么直接统计答案就好了}else{f[v][0] += max(f[u][0], f[u][1]); // 正常的树上最大独立集dpf[v][1] += f[u][0];ind[v] --;if(ind[v] == 0){q.push(v);}}}// 遍历剩下的入度不为0的结点(说明在环上)for(int i = 1; i <= n; i ++){if(ind[i] >= 1 && !vis[i]){vector<int> ring;ring.push_back(0); // 让下标从1开始int u = i;while(!vis[u]){ // 从一个点一直走,直到回到自己,就说明跑完了一整个环vis[u] = true;ring.push_back(u);u = a[u];}int len = ring.size() - 1;vector<vector<ll>> g(len + 1, {0, 0}); // g[i][1/0]表示结点i选/不选的最大答案(i在环上)// 首先钦定最后一个不选,则第一个选不选都行g[1][0] = f[ring[1]][0], g[1][1] = f[ring[1]][1];for(int j = 2; j <= len; j ++){g[j][0] = max(g[j - 1][0], g[j - 1][1]) + f[ring[j]][0];g[j][1] = g[j - 1][0] + f[ring[j]][1];}ll res1 = g[len][0];// 然后钦定第一个不选,则最后一个选不选都行g[1][0] = f[ring[1]][0], g[1][1] = -inf; // 初始化第一个选的收益为负无穷,相当于强制不选第一个for(int j = 2; j <= len; j ++){g[j][0] = max(g[j - 1][0], g[j - 1][1]) + f[ring[j]][0];g[j][1] = g[j - 1][0] + f[ring[j]][1];}ll res2 = max(g[len][0], g[len][1]);ans += max(res1, res2);}}cout << ans << '\n';return 0;
}
相关文章:
题解:P11501 [ROIR 2019] 探险队(Day 2)
前言:这道题 dp 做法找环的部分还没有用拓扑做的,补充一下。 这道题其实很像“上司的舞会”,就是求树上最大独立集。 这里我们把每个人向他讨厌的那个人连边(发现所有点出度均为 1 1 1,所以这是一个基环树࿰…...
读者写者问题与读写锁自旋锁
一、读者写者问题 读者写者问题具有以下特点: 一个交易场所---写者写入数据,读者读数据两种角色---读者,写者三种关系 读者和读者---并发写者和写者---互斥读者和写者---互斥 && 同步 二、读者写者VS生产消费 生产者消费者模型中…...
Sublime text启用vim
打开:首选项 > 设置,在打开的输入框中把 "ignored_packages": ["Vintage"] 修改为 "ignored_packages": [],不忽略Vintage,即为启用Vintage,它是Sublime的内置vim插件。 然后再添加&…...
蚂蚁百宝箱快速创建智能体AI小程序
蚂蚁百宝箱官网https://tbox.alipay.com/community?operationSource1006/ 以下是一篇关于蚂蚁百宝箱快速创建智能体 AI 小程序的图文并茂的博客: 标题:蚂蚁百宝箱快速创建智能体 AI 小程序,开启智能应用新体验 引言 在数字化飞速发展的当…...
【Anconda安装教程】安装到环境配置全流程
目录 前言 一、进入官网下载 二、下载Anconda编辑 三、安装Anconda 四、配置环境变量 五、验证是否安装成功 六、anaconda的使用 情况一:电脑现在没有装python或者现在装的可以卸载掉 情况二:电脑目前装了python,但想保留它 6.1 进…...
Linux系统编程 | IPC对象---信号量
在前面两篇博客文章中,对Linux系统编程部分IPC三大对象中的消息队列和共享内存的知识体系做了一个大致的梳理,在本篇文章中,将对三大IPC对象中的最后一个信号量做一个总结。如果有需要的博客朋友,可以参考我的Linux系统编程专栏参…...
当数据自己会说话:聚类与分类算法全景解析
从金融风控到医疗诊断,两种机器学习技术如何重塑决策逻辑 在人工智能与数据驱动的时代,聚类和分类作为机器学习的两大核心技术,已成为从海量数据中提取价值的必备工具。它们看似相似——都是将数据划分到不同的组中——但内在逻辑和应用场景却…...
哈佛结构(Harvard Architecture)与冯·诺依曼架构(Von Neumann Architecture)
一、基础概念与历史溯源 哈佛结构 起源:1940年代由哈佛大学开发的Mark I计算机首次采用,专为弹道计算优化。核心特征: 物理分离的存储器:程序指令存储在ROM/Flash,数据存储在RAM,两者独立编址。独立总线系统…...
Python内存使用分析工具深度解析与实践指南(下篇)
文章目录 引言6. guppy3 / Heapy功能安装程序示例适用场景注意事项 7. objgraph功能安装程序示例适用场景注意事项 8. memory_profiler功能安装程序示例适用场景注意事项 9. profile(标准库)功能程序示例适用场景注意事项 总结对比表 引言 在Python编程…...
经典控制理论:线性化笔记
一、弹簧阻尼系统 求B点的位置X0,与弹簧形变后的位置X1的关系 ---- 解: 二、直流电动机模型 求输出转速与输入电压的关系 解:...
【StarRocks系列】查询优化
步骤参考官网 分析查询 | StarRocks StarRocks-Profile分析及优化指南 StarRocks-Profile分析及优化指南 - 经验教程 - StarRocks中文社区论坛...
【STM32】STM32的中断系统寄存器NVIC、EXTI
文章目录 中断概述中断的概念为什么需要中断STM32的中断 STM32的中断体系架构NVICNVIC的介绍中断优先级优先级寄存器优先级组 EXTI 中断概述 中断的概念 在主程序运行过程中,出现了特定事件,使得CPU暂停当前正在运行的程序,转而去处理这个事…...
LLM-201: OpenHands与LLM交互链路分析
一、核心交互链路架构 #mermaid-svg-ZBqCSQk1PPDkIXNx {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-ZBqCSQk1PPDkIXNx .error-icon{fill:#552222;}#mermaid-svg-ZBqCSQk1PPDkIXNx .error-text{fill:#552222;strok…...
税务 VR 虚拟体验,带来全新办税感受
在过去,企业办税难题诸多。申报纳税高峰期,办税服务厅人满为患,财务人员需早起取号排队,耗费大量时间。传统办税流程复杂,涉及多环节和部门,资料繁多,若准备不全或有误就得重新准备,…...
【Linux 驱动中断】
Linux 驱动中断 一、GIC 控制器:硬件中断的枢纽二、GPIO 中断:设备交互的常见入口三、Tasklet 与软中断:高效的异步处理机制3.1 Tasklet3.2 软中断 四、工作队列:灵活的任务处理框架4.1 共享工作队列4.2 自定义工作队列4.3 延迟工…...
ali 轻量服务器安装nginx
# Ubuntu sudo apt install nginx-light # 精简版 # CentOS sudo yum install nginx #启动并设置开机自启 sudo systemctl daemon-reload sudo systemctl start nginx sudo systemctl enable nginx #验证安装 nginx -v curl -I 127.0.0.1 #常用命令: # 重新加载配…...
2025年- H83-Lc191--139.单词拆分(动态规划)--Java版
1.题目描述 2.思路 字符串s是一个容器(一个背包),wordDict词典是物品,这里面的每个物品我们可以使用多次。 动归五部曲 (1)字符串的长度为i,dp[i]true。 dp[s.size] dp[0]代表空字符串 &#x…...
【好用但慎用】Windows 系统中将所有 WSL 发行版从 C 盘迁移到 非系统 盘的完整笔记(附 异常处理)
🚀 将所有 WSL 发行版从 C 盘迁移到 I 盘的完整教程(含 Podman / NVIDIA Workbench / Ubuntu 等) 【无标题】使用 Chocolatey 安装 WSL 管理工具 LxRunOffline-CSDN博客 免责声明 重要提示 在执行 WSL 迁移操作前,请务必仔细阅读…...
贪心算法思路详解
文章目录 一、贪心算法是什么?二、贪心算法原理三、再谈背包问题四、活动选择问题五、拟阵理论总结 一、贪心算法是什么? 贪心算法与动态规划算法一样是用于求解最优化类问题的算法,其本质上是基于动态规划算法的改进算法,其所求…...
Keil 安装 CMSIS-FreeRTOS 失败解决方案
一、问题现象 在 Keil 中安装 CMSIS-FreeRTOS 时出现以下错误: (1) 通过内置工具安装: (2)通过官网安装: 二、核心原因 Keil 版本过低,与 CMSIS-FreeRTOS 包不兼容: …...
Python打卡DAY33
DAY33:MLP神经网络的训练 恩师浙大疏锦行 知识点: PyTorch和cuda的安装查看显卡信息的命令行命令(cmd中使用)cuda的检查简单神经网络的流程 数据预处理(归一化、转换成张量)模型的定义 继承nn.Module类定义…...
RJ45 网口实现千兆传输速率(1Gbps)的原理,涉及物理层传输技术、线缆标准、信号调制及网络协议等多方面的协同设计。以下从技术维度展开详细解析:
一、千兆以太网的标准与物理层基础 1. 标准规范 千兆以太网遵循 IEEE 802.3ab(针对双绞线)和 IEEE 802.3z(针对光纤)标准,其中 RJ45 接口对应双绞线场景,核心是通过四对双绞线(CAT5e/CAT6 线缆…...
leetcode hot 100之:二叉树的层序遍历
层序遍历和前中后序遍历不一样,大家可以想象的是:前中后序遍历可以用递归,因为他是以子树为标准来选择的;那层序怎么办呢?怎么才能一层层地遍历呢? void First(TreeNode* root) {printf("%d",ro…...
深入解析BERT:语言分类任务的革命性引擎
“BERT的出现,如同在自然语言处理领域投下了一颗认知炸弹——它让机器真正学会了’联系上下文’。” ——自然语言处理研究者普遍共识 在自然语言处理(NLP)领域,2018年诞生的BERT(Bidirectional Encoder Representatio…...
Pycharm中Jupyter Notebook 插件常用快捷键
bg:Jupyter跟LINQPad很像,都是方便写的时候看数据用 快捷键功能Shift Enter执行当前单元格,并跳转到下一个单元格Ctrl Enter执行当前单元格,不跳转(留在当前单元格)Alt Enter执行当前单元格,…...
【Python】Excel表格操作:ISBN转条形码
一、效果 原始文件: 输出文件: 二、代码 import os import logging from openpyxl import load_workbook from openpyxl.drawing.image import Image as ExcelImage from barcode import EAN13 from barcode.writer import ImageWriterlogging.basicCo…...
大数据Hadoop集群搭建
文章目录 大数据Hadoop集群搭建一、VMware准备Linux虚拟机二、VMware虚拟机系统设置1、主机名、IP、SSH免密登录2、JDK环境部署3、防火墙、SELinux、时间同步 三、VMware虚拟机集群上部署HDFS集群1、集群规划2、上传&解压3、Hadoop安装包目录结构4、修改配置文件࿰…...
饼图:数据可视化的“切蛋糕”艺术
饼图,作为数据可视化家族中最经典、最易识别的成员之一,其核心功能如同其名——像切分蛋糕一样,直观展示一个整体(100%)被划分为若干组成部分的比例关系。 往期文章推荐: 20.用Mermaid代码画ER图:AI时代的…...
mysql server层做了什么
服务器处理客户端请求 服务器程序在处理来自客户端的查询请求时,大致需要分为3部分:连接管理、解析与优化、存储引擎。 连接管理 每当有一个客户端进程连接到服务器进程时,服务器进程都会创建一个线程专门处理与这个客户端的交互ÿ…...
3.5.1_1 信道划分介质访问控制(上)
在这个视频中我们要介绍信道划分、介质访问控制,这是两个词,我们先介绍一下什么叫做介质访问控制。 通过之前的学习,我们知道在计算机网络当中,有的信道它在逻辑上属于总线型,我们也可以把这种信道称为广播信道&#x…...
RPC常见问题回答
项目流程和架构设计 1.服务端的功能: 1.提供rpc调用对应的函数 2.完成服务注册 服务发现 上线/下线通知 3.提供主题的操作 (创建/删除/订阅/取消订阅) 消息的发布 2.服务的模块划分 1.网络通信模块 net 底层套用的moude库 2.应用层通信协议模块 1.序列化 反序列化数…...
数据分析和可视化:Py爬虫-XPath解析章节要点总结
重要知识点 XPath 概述:XPath 是一门可以在 XML 文件中查找信息的语言,也可用于 HTML 文件。它功能强大,提供简洁明了的路径表达式和多个函数,用于字符串、数值、时间比较等。1999 年成为 W3C 标准,常用于爬虫中抓取网…...
WIFI原因造成ESP8266不断重启的解决办法
一、报错 报错信息如下: 21:37:21.799 -> ets Jan 8 2013,rst cause:2, boot mode:(3,7) 21:37:21.799 -> 21:37:21.799 -> load 0x4010f000, len 3424, room 16 21:37:21.799 -> tail 0 21:37:21.799 -> chksum 0x2e 21:37:21.799 -> loa…...
OSI网络通信模型详解
OSI 模型就是把这整个过程拆解成了 7 个明确分工的步骤,每一层只负责自己那一摊事儿,这样整个系统才能顺畅运转,出了问题也容易找到“锅”在谁那。 核心比喻:寄快递 📦 想象你要把一份重要的礼物(你的数据…...
第五章 中央处理器
5.1 CPU的功能和基本构造 5.1.1 CPU的基本功能 5.1.2 CPU的基本结构 1.运算器 算术逻辑单元ALU 累加寄存器ACC 程序字状态寄存器PSW 计数器CT 暂存寄存器 通用寄存器组 移位器 通用寄存器供用户自由编程,可以存放数据和地址。而指令寄存器是专门用于存放指令的专用寄存器,…...
大模型学习入门——Day3:注意力机制
本系列笔记的教材:快乐学习大模型-DataWhale团队 注意力机制 注意力机制最先源于计算机视觉领域,其核心思想为当我们关注一张图片,我们往往无需看清楚全部内容而仅将注意力集中在重点部分即可。而在自然语言处理领域,我们往往也…...
C++ 学习笔记精要(二)
第一节 特殊类的设计 1. 一个类: 只能在堆上创建对象 关键点:自己控制析构 1.1 方法一: 使用delete禁掉默认析构函数 #include <iostream> using namespace std;class HeapOnly { public:HeapOnly(){_str new char[10];}~HeapOnly() delete;void Destroy(){delete[…...
博士,超28岁,出局!
近日,长沙市望城区《2025年事业引才博士公开引进公告》引发轩然大波——博士岗位年龄要求28周岁及以下,特别优秀者也仅放宽至30周岁。 图源:网络 这份规定让众多"高龄"博士生直呼不合理,并在社交平台掀起激烈讨论。 图源…...
macOS - 根据序列号查看机型、保障信息
文章目录 最近在看 MacBook 二手机,有个咸鱼卖家放个截图 说不清参数,于是想根据 序列号 查看机型。苹果提供了这样的网页: https://checkcoverage.apple.com/ (无需登录) 结果 2025-06-20(五)…...
C/C++ 高频八股文面试题1000题(一)
原作者:Linux教程,原文地址:C/C 高频八股文面试题1000题(一) 在准备技术岗位的求职过程中,C/C始终是绕不开的核心考察点。无论是互联网大厂的笔试面试,还是嵌入式、后台开发、系统编程等方向的岗位,C/C 都…...
C++ map 和 unordered_map 的区别和联系
C map 和 unordered_map 的区别和联系 map 和 unordered_map 都是 C 标准库中关联容器,用于存储键值对。它们的主要区别在于底层实现和性能特性,联系在于它们都提供了键值对的存储和访问功能。 区别: 特性mapunordered_map底层实现红黑树 …...
Sentinel实现原理
Sentinel 是阿里巴巴开源的分布式系统流量控制组件,主要用于服务保护,涵盖流量控制、熔断降级、系统负载保护等功能。 以下是 Sentinel 的实现原理,使用中文简要说明: 1. 总体架构 Sentinel 采用 轻量级 设计,分为 核…...
python打卡day37
疏锦行 知识点回顾: 1. 过拟合的判断:测试集和训练集同步打印指标 2. 模型的保存和加载 a. 仅保存权重 b. 保存权重和模型 c. 保存全部信息checkpoint,还包含训练状态 3. 早停策略 作业:对信贷数据集训练后保存权重…...
MySQL复杂查询优化实战:从多表关联到子查询的性能突破
文章目录 一、复杂查询性能瓶颈分析与优化框架二、多表关联查询的优化策略与实战1. JOIN顺序优化:基于成本估算的表关联策略2. 复合索引与JOIN条件优化3. 大表JOIN的分片处理 三、子查询优化:从嵌套到JOIN的转换艺术1. 标量子查询转换为JOIN2. EXISTS子查…...
LeetCode 680.验证回文串 II
目录 题目: 题目描述: 题目链接: 思路: 核心思路: 思路详解: 代码: C代码: Java代码: 题目: 题目描述: 题目链接: 680. 验证…...
window显示驱动开发—输出合并器阶段
逻辑管道中的最后一步是通过模具或深度确定可见性,以及写入或混合输出以呈现目标,这可以是多种资源类型之一。 这些操作以及输出资源 (呈现目标) 绑定在输出合并阶段定义。 1. 核心功能与管线定位 输出合并是渲染管线的最终固定功能阶段,负…...
单片机开发日志cv MDK-ARM工具链迁移到MAKE
核心经验: STM32H7 多 RAM 区域,外设相关数据段必须放在 AXI SRAM(RAM)区,不能放在 DTCMRAM,否则外设无法访问,程序表面正常但外设全失效。迁移工程时,务必检查链接脚本的内存分布&a…...
大模型与搜索引擎的技术博弈及未来智能范式演进
基于认知革命与技术替代的全景综述 一、大模型对搜索引擎的替代性分析:技术范式与市场重构 (1)技术原理的代际分野 传统搜索引擎遵循 "爬虫抓取 - 索引构建 - 关键词排序" 的三段式架构,其核心是基于 PageRank 算法的…...
Ajax-入门
Ajax: 全称Asynchronous JavaScript And XML,异步的JavaScript和XML。其作用有如下2点: 与服务器进行数据交换:通过Ajax可以给服务器发送请求,并获取服务器响应的数据。 异步交互:可以在不重新加载整个页面的情况下&a…...
FPGA基础 -- Verilog 共享任务(task)和函数(function)
Verilog 中共享任务(task)和函数(function) 的详细专业培训,适合具有一定 RTL 编程经验的工程师深入掌握。 一、任务(task)与函数(function)的基本区别 特性taskfunctio…...