[Daimayuan] 树(C++,动态规划,01背包方案数)
有一棵 n n n 个节点的以 1 1 1 号点为根的有根树。现在可以对这棵树进行若干次操作,每一次操作可以选择树上的一个点然后删掉连接这个点和它的儿子的所有边。
现在我们想知道对于每一个 k k k ( 1 ≤ k ≤ n 1≤k≤n 1≤k≤n),最少需要多少次操作能让图中恰好存在 k k k 个联通块。
输入格式
第一行输入一个正整数 n n n。
第二行输入 n − 1 n−1 n−1 个整数 f 1 , f 2 , . . . , f n − 1 f_1,f_2,...,f_{n−1} f1,f2,...,fn−1, f i f_i fi 表示 i + 1 i+1 i+1 号点的父亲,保证 1 ≤ f i ≤ i 1≤f_i≤i 1≤fi≤i。
输出格式
输出 n n n 个整数,第 i i i 个数表示 k = i k=i k=i 时的答案,如果无法让图中恰好存在 i i i 个联通块,则输出 -1。
样例输入1
6
1 2 1 1 2
样例输出1
0 -1 1 1 -1 2
数据规模
共 10 10 10 个测试点。
测试点 1 , 2 , 3 1,2,3 1,2,3 满足 n ≤ 20 n≤20 n≤20。
测试点 4 , 5 , 6 4,5,6 4,5,6 满足 n ≤ 100 n≤100 n≤100。
对于所有数据,满足 1 ≤ n ≤ 3000 1≤n≤3000 1≤n≤3000。
解题思路
对于一棵树来说,删去任意一条边都会使连通块数目 + 1 +1 +1。
那么要判断能否得到 k k k个连通块,我们只需要判断能否恰好删去 k − 1 k-1 k−1条边。
题目要求操作为:删除一个节点与子节点之间的所有边。
那么统计每个节点的子节点数目,然后就变为了01背包可行性问题:
每一个节点都是一个物品,问能否恰好装满容量为 k − 1 k-1 k−1的背包?
for (int i = 1; i <= n; i++) {//尝试每一个物品for (int j = 0; j < n; j++) {//尝试新的重量组合if (j - items[i] >= 0)ans[i][j] = ans[i - 1][j] || ans[i - 1][j - items[i]];elseans[i][j] = ans[i - 1][j];}
}
以上我们只是检验了可行性问题,但是题目中还有另外一个要求:操作次数最少。
因为在物品组合中没有先后顺序,所以我们可以通过物品组合中的物品数量来确定操作次数。
只有新的操作次数小于旧的操作次数的时候,我们才进行更新。
for (int i = 1; i <= n; i++) {//尝试每一个物品for (int j = 0; j < n; j++) {//尝试新的重量组合if (j - items[i] >= 0 && ans[i - 1][j] && ans[i - 1][j - items[i]])ans[i][j] = min(ans[i - 1][j], ans[i - 1][j - items[i]] + 1);else if (ans[i - 1][j])ans[i][j] = ans[i - 1][j];else if (j - items[i] >= 0 && ans[i - 1][j - items[i]])ans[i][j] = ans[i - 1][j - items[i]];}
}
注:1)以上代码段中,ans中元素的含义发生了变化:可行/不可行 -> 物品数量;
2)为了与不存在的组合(ans[i][j] = 0)相区分,我们为所有存在的组合物品数量添加偏置bias,也就是说,物品数量 = ans[i][j] - bias。
以上代码的空间复杂度、时间复杂度均可以接受,可以AC,接下来是优化部分qwq。
因为嫌弃这个算法的空间复杂度,所以我们对其进行优化,压缩到二维数组:
for (int i = 1; i <= n; i++) {//尝试每一个物品for (int j = 0; j < n; j++) {//尝试新的重量组合if (j - items[i] >= 0 && ans[(i - 1) % 2][j] && ans[(i - 1) % 2][j - items[i]])ans[i % 2][j] = min(ans[(i - 1) % 2][j], ans[(i - 1) % 2][j - items[i]] + 1);else if (ans[(i - 1) % 2][j])ans[i % 2][j] = ans[(i - 1) % 2][j];else if (j - items[i] >= 0 && ans[(i - 1) % 2][j - items[i]])ans[i % 2][j] = ans[(i - 1) % 2][j - items[i]];}
}
还是嫌弃?继续压,压缩到一维数组:
for (int i = 1; i <= n; i++) {//尝试每一个物品for (int j = n; j >= items[i]; j--) {//尝试新的重量组合if (j - items[i] >= 0 && ans[j] && ans[j - items[i]])ans[j] = min(ans[j], ans[j - items[i]] + 1);else if (ans[j]) ans[j] = ans[j];else if (j - items[i] >= 0 && ans[j - items[i]])ans[j] = ans[j - items[i]] + 1;}
}
然后我们删除一些无用的部分:
for (int i = 1; i <= n; i++) {//尝试每一个物品for (int j = n; j >= items[i]; j--) {//尝试新的重量组合if (ans[j] && ans[j - items[i]]) ans[j] = min(ans[j], ans[j - items[i]] + 1);else if (ans[j - items[i]]) ans[j] = ans[j - items[i]] + 1;}
}
嗯,好看多了qwq。
最后,AC代码如下:
#include <iostream>
using namespace std;
const int max_n = 3000;int ans[max_n + 1], n;
int items[max_n + 1];int main() {cin >> n;int fa;for (int i = 1; i < n; i++) {cin >> fa;items[fa]++;}int bias = 1;ans[0] = bias;for (int i = 1; i <= n; i++) {//尝试每一个物品for (int j = n; j >= items[i]; j--) {//尝试新的重量组合if (ans[j] && ans[j - items[i]]) ans[j] = min(ans[j], ans[j - items[i]] + 1);else if (ans[j - items[i]]) ans[j] = ans[j - items[i]] + 1;}}cout << 0;for (int i = 2; i <= n; i++) {cout << ' ' << ans[i - 1] - bias;}return 0;
}相关文章:
[Daimayuan] 树(C++,动态规划,01背包方案数)
有一棵 n n n 个节点的以 1 1 1 号点为根的有根树。现在可以对这棵树进行若干次操作,每一次操作可以选择树上的一个点然后删掉连接这个点和它的儿子的所有边。 现在我们想知道对于每一个 k k k ( 1 ≤ k ≤ n 1≤k≤n 1≤k≤n),最少需要多少次操作能…...
如何选择源代码加密软件
(SDC沙盒)和DLP、文档加密、云桌面等,其优缺点做客观比较如下: 比较内容安全容器(SDC沙盒)DLP文档加密云桌面代表厂家*信达卖咖啡、赛门贴科亿*通、IP噶德、*盾、*途四杰、深*服设计理念以隔离容器加准入技术为基础,构…...
TO-B类软件产品差异化
产品差异化,是在市场众多同质化产品中,突出自身产品亮点的重要方式。对于客户来讲其选择是多种多样的,与其花费大量的时间研究每一家产品的特点,还不如直接选择品牌更大、价格更低的产品来的直接,因此显而易见的突出产…...
设计模式之美-实战一(上):业务开发常用的基于贫血模型的MVC架构违背OOP吗?
领域驱动设计(Domain Driven Design,简称DDD)盛行之后,这种基于贫血模型的传统的开发模式就更加被人诟病。而基于充血模型的DDD开发模式越来越被人提倡。所以,我打算用两节课的时间,结合一个虚拟钱包系统的…...
ChatGPT如何训练自己的模型
ChatGPT是一种自然语言处理模型,它的任务是生成自然流畅的对话。如果想要训练自己的ChatGPT模型,需要进行大量的数据收集、预处理、配置训练环境、模型训练、模型评估等过程。本文将详细介绍这些过程,帮助读者了解如何训练一个高品质的ChatGP…...
springboot使用线程池的实际应用(一)
在实际Spring Boot项目中,我们可以使用Java的原生多线程或者使用Spring自带的线程池进行多线程编程。多线程的好处在于能够提高应用程序的运行效率,特别是在某些计算密集型场景下。以下是一些使用多线程的典型场景: 并发处理请求:…...
ESP-8266学习笔记
1、学习地址 【XMF09F系列资源】基于MicroPython的ESP8266物联网应用开发-赛教资源目录汇总-小蜜蜂笔记 Quick reference for the ESP8266 — MicroPython latest documentation 2、MicroPython及相关开发资源 3、固件烧录与uPyLoader的使用 烧录教程参考: https://www.…...
Java泛型简单的使用
前言 Java里面的泛型在实际开发中运用的很多,学过C的同学一定知道C的模板,而Java中的泛型,一定程度上和它还是挺像的。 相信写Java的人,大都有用过List的实现类ArrayList。在Java没有泛型之前,它的内部是一个Object的…...
深度探索:Qt CMake工程编译后的自动打包策略
深度探索:Qt CMake工程编译后的自动打包策略 1. 引言(Introduction)1.1 Qt和CMake的基本概念(Basic Concepts of Qt and CMake)1.2 自动打包的重要性(Importance of Automatic Packaging) 2. Qt…...
2.7 编译型和解释型
2.7 编译型和解释型 前面我们使用java和javac命令把Hello,World!在控制台输出。那为什么输出,这里我们需要掌握两个知识点。编译型语言和解释型语言。在计算机的高级编程语言就分为编译型语言和解释型语言。而我们的Java既有编译型的特点也有…...
校园网自动登陆(河南科技学院)
1. 介绍 河南科技学院校园网自动登陆(新乡的很多系统相似,可能也可以用?),java版。可以实现电脑,路由器,软路由的自动认证wifi,后续会上传docker版本的。 源码地址 github:https://…...
C++11 override和final关键字
C11中的override和final关键字是为了增强代码的编译时类型检查和面向对象设计中的继承机制。 override关键字用于显示地表明派生类中的成员函数覆盖了基类中的虚函数。当派生类中的函数与基类中的虚函数签名不同或者没有使用override关键字时,编译器会给出警告或错…...
kafka的log存储解析
kafka的log存储解析——topic的分区partition分段segment以及索引等 引言Kafka中的Message是以topic为基本单位组织的,不同的topic之间是相互独立的。每个topic又可以分成几个不同的partition(每个topic有几个partition是在创建topic时指定 的),每个…...
4.文件系统
组成 Linux:一切皆文件 索引节点(I-node) I-node(Index Node):文件系统的内部数据结构,用于管理文件的元数据和数据块。 文件的元数据:包括文件的权限、拥有者、大小、时间戳、索引…...
Shell脚本case in esac分支语句应用
记录:434 场景:Shell脚本case in esac分支语句应用。 版本:CentOS Linux release 7.9.2009。 1.case in esac格式 格式: case 值 in 模式1)expression;; 模式2)expression;; 模式n)expression;; esac 解析:case…...
【线性dp必学四道题】线性dp四道经典例题【最长上升子序列】、【最长公共子序列】、【最长公共上升子序列(maxv的由来)】【最长公共子串】
【最长上升子序列】、【最长公共子序列】、【最长公共上升子序列】 最长上升子序列f[i] 表示以i结尾的最长子序列 最长公共子序列f[i][j] 表示 a前i 和 b前j个 最长公共长度 最长公共上升子序列f[i][j]代表所有a[1 ~ i]和b[1 ~ j]中以b[j]结尾的公共上升子序列的集合 最长公共子…...
追寻幸福:探索幸福的关键特征和行为
目录 1. 积极的心态 2. 良好的人际关系 3. 自我接纳和自尊 4. 追求意义和目标 5. 健康的身心状态 6. 感知和实现个人价值 幸福是一个主观的感受,因此不同的人对于幸福的定义和追求方式可能会有所不同。然而,有一些共同的特点和行为模式,…...
Redis-02-集群
一、redis5搭建集群 1.1、案例:搭建6台redis主机,配置如下 redis并发量:https://www.gxlcms.com/redis-350423.html主机IP:192.168.168.60~65修改redis配置文件hash槽移动,槽内的数据也随之移动 [root60 ~]# vim /e…...
【2023 · CANN训练营第一季】MindSpore模型快速调优攻略 第三章——MindSpore云上调试调优
1.ModelArts云上调试调优 ModelArts密钥初始化 详细教程: 初始化OBS服务 创建训练作业 2.MindSpore IDE插件效率提升 通过智能代码块推荐、代码自动补全等特性,提升MindSpore脚本开发效率,对接ModelArts云服务,实现模型训…...
python笔记17_实例演练_二手车折旧分析p2
…… 书接上文 4.车辆等级维度 探查车龄为5年的车辆,折旧价值与车辆等级的关系。 # 筛选出车龄为5的数据创建新表 data_age5 data[data[age] 5] data_age5 # 分组聚合计算均值 data_car_level data_age5.groupby(car_level_name)[lowest_price].mean().reset…...
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility
Cilium动手实验室: 精通之旅---20.Isovalent Enterprise for Cilium: Zero Trust Visibility 1. 实验室环境1.1 实验室环境1.2 小测试 2. The Endor System2.1 部署应用2.2 检查现有策略 3. Cilium 策略实体3.1 创建 allow-all 网络策略3.2 在 Hubble CLI 中验证网络策略源3.3 …...
人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式
今天是关于AI如何在教学中增强学生的学习体验,我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育,这并非炒作,而是已经发生的巨大变革。教育机构和教育者不能忽视它,试图简单地禁止学生使…...
基于SpringBoot在线拍卖系统的设计和实现
摘 要 随着社会的发展,社会的各行各业都在利用信息化时代的优势。计算机的优势和普及使得各种信息系统的开发成为必需。 在线拍卖系统,主要的模块包括管理员;首页、个人中心、用户管理、商品类型管理、拍卖商品管理、历史竞拍管理、竞拍订单…...
Go 并发编程基础:通道(Channel)的使用
在 Go 中,Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式,用于在多个 Goroutine 之间传递数据,从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...
基于PHP的连锁酒店管理系统
有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发,数据库mysql,前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...
Modbus RTU与Modbus TCP详解指南
目录 1. Modbus协议基础 1.1 什么是Modbus? 1.2 Modbus协议历史 1.3 Modbus协议族 1.4 Modbus通信模型 🎭 主从架构 🔄 请求响应模式 2. Modbus RTU详解 2.1 RTU是什么? 2.2 RTU物理层 🔌 连接方式 ⚡ 通信参数 2.3 RTU数据帧格式 📦 帧结构详解 🔍…...
Python学习(8) ----- Python的类与对象
Python 中的类(Class)与对象(Object)是面向对象编程(OOP)的核心。我们可以通过“类是模板,对象是实例”来理解它们的关系。 🧱 一句话理解: 类就像“图纸”,对…...
CTF show 数学不及格
拿到题目先查一下壳,看一下信息 发现是一个ELF文件,64位的 用IDA Pro 64 打开这个文件 然后点击F5进行伪代码转换 可以看到有五个if判断,第一个argc ! 5这个判断并没有起太大作用,主要是下面四个if判断 根据题目…...
五、jmeter脚本参数化
目录 1、脚本参数化 1.1 用户定义的变量 1.1.1 添加及引用方式 1.1.2 测试得出用户定义变量的特点 1.2 用户参数 1.2.1 概念 1.2.2 位置不同效果不同 1.2.3、用户参数的勾选框 - 每次迭代更新一次 总结用户定义的变量、用户参数 1.3 csv数据文件参数化 1、脚本参数化 …...
python读取SQLite表个并生成pdf文件
代码用于创建含50列的SQLite数据库并插入500行随机浮点数据,随后读取数据,通过ReportLab生成横向PDF表格,包含格式化(两位小数)及表头、网格线等美观样式。 # 导入所需库 import sqlite3 # 用于操作…...
