[Daimayuan] 树(C++,动态规划,01背包方案数)

news/2024/4/24 5:53:44/

有一棵 n n n 个节点的以 1 1 1 号点为根的有根树。现在可以对这棵树进行若干次操作,每一次操作可以选择树上的一个点然后删掉连接这个点和它的儿子的所有边。

现在我们想知道对于每一个 k k k ( 1 ≤ k ≤ n 1≤k≤n 1kn),最少需要多少次操作能让图中恰好存在 k k k 个联通块。

输入格式

第一行输入一个正整数 n n n

第二行输入 n − 1 n−1 n1 个整数 f 1 , f 2 , . . . , f n − 1 f_1,f_2,...,f_{n−1} f1,f2,...,fn1 f i f_i fi 表示 i + 1 i+1 i+1 号点的父亲,保证 1 ≤ f i ≤ i 1≤f_i≤i 1fii

输出格式

输出 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 n20

测试点 4 , 5 , 6 4,5,6 4,5,6 满足 n ≤ 100 n≤100 n100

对于所有数据,满足 1 ≤ n ≤ 3000 1≤n≤3000 1n3000

解题思路

对于一棵树来说,删去任意一条边都会使连通块数目 + 1 +1 +1

那么要判断能否得到 k k k个连通块,我们只需要判断能否恰好删去 k − 1 k-1 k1条边。

题目要求操作为:删除一个节点与子节点之间的所有边。

那么统计每个节点的子节点数目,然后就变为了01背包可行性问题:

每一个节点都是一个物品,问能否恰好装满容量为 k − 1 k-1 k1的背包?

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;
}

http://www.ppmy.cn/news/79328.html

相关文章

一文告诉你黑盒测试、白盒测试、集成测试和系统测试的区别与联系

于开发人员来说&#xff0c;往往对各种测试方法感到疑惑。特别是在整合代码的时候&#xff0c;我们就能深刻感觉受到测试的重要性。很多开发人员只注重写代码&#xff0c;轻视测试的重要性。总是代码一写完提交然后就交给测试组测试了&#xff0c;没多久测试组发回测试报告。然…

[CTF/网络安全] 攻防世界 xff_referer 解题详析

[CTF/网络安全] 攻防世界 xff_referer 解题详析 XFF及refererXFF格式referer格式姿势总结 题目描述&#xff1a;X老师告诉小宁其实xff和referer是可以伪造的。 XFF及referer X-Forwarded-For&#xff08;简称 XFF&#xff09;是一个 HTTP 请求头部字段&#xff0c;它用于表示 …

Python共享文件 - Python快速搭建HTTP web服务实现文件共享并公网远程访问

文章目录 1. 前言2. 视频教程3. 本地文件服务器搭建3.1 python的安装和设置3.2 cpolar的安装和注册 4. 本地文件服务器的发布4.1 Cpolar云端设置4.2 Cpolar本地设置 5. 公网访问测试6. 结语 转载自内网穿透工具的文章&#xff1a;Python一行代码实现文件共享【内网穿透公网访问…

【用python的QT做信号处理的界面】

文章目录 入口文件界面参数调整数据从dat解析出来的文件从界面点击打开文件夹的功能实现主要功能代码网络参数存图替换功能&#xff0c;比如把倒频谱替换成倒频谱2 入口文件 入口文件&#xff0c;主要用来实例化窗口&#xff08;不重要&#xff09;&#xff0c;只要知道从这里…

【Cpp】哈希之手撕闭散列/开散列

文章目录 unorderedunordered系列关联式容器unordered_map和unordered_set概述unordered_map的文档介绍unordered_map的接口说明 底层结构 哈希哈希/散列表 概念哈希冲突哈希函数哈希函数设计原则&#xff1a;常见哈希函数 哈希冲突解决闭散列线性探测二次探测 开散列 哈希表的…

这个 归并排序详解过程 我能吹一辈子!!!

文章目录 归并排序概念归并排序算法思路归并排序递归实现归并排序非递归实现 归并排序概念 1945年&#xff0c;约翰冯诺依曼&#xff08;John von Neumann&#xff09;发明了归并排序&#xff0c;这是典型的分治算法的应用。 归并排序&#xff08;Merge sort&#xff09;是建立…

ASEMI代理长电可控硅MCR100-8特征,MCR100-8应用

编辑-Z 长电可控硅MCR100-8参数&#xff1a; 型号&#xff1a;MCR100-8 VDRM/VRRM&#xff1a;600V IT(RMS)&#xff1a;0.8A 结点温度Tj&#xff1a;-40~125℃ 储存温度Tstg&#xff1a;-55 ~ 150℃ 通态电压VTM&#xff1a;1.7V 栅极触发电压VGT&#xff1a;0.8V 正…

【网络】- TCP/IP四层(五层)协议 - 网际层(网络层) - 网际协议IP

目录 一、概述 二、初步了解网际协议 IP  &#x1f449;2.1 与数据链路层的区别  &#x1f449;2.2 网际协议 IP 概览  &#x1f449;2.3 分层的意义 三、IP协议基础知识  &#x1f449;3.1 IP地址属于网络层地址  &#x1f449;3.2 路由控制  &#x1f449;3.3 IP分包与…

优化器| SGD/Adam/

前言&#xff1a;最近准备复习一下深度学习的基础知识&#xff0c;开个专栏记录自己的学习笔记 各种SGD和Adam优化器整理 基本概念 优化&#xff1a;最大化或最小化目标函数&#xff0c;具体指最小化代价函数或损失函数 损失函数 J(θ)f(hθ(x)&#xff0c;y)&#xff0c;h…

2023系统分析师---冲刺资料必备知识点三

视图的优点&#xff1a; 视图能简化用户的操作&#xff1b;视图机制可以使用户以不同的方式查询同一数据&#xff1b;视图对数据库重构提供了一定程度的逻辑独立性&#xff1b;视图可以对机密的数据提供安全保护&#xff1b; ER图、实体、联系、联系的类型&#xff1a; 分布…

内置类型转换

在 C 中&#xff0c;内置类型之间存在一定的隐式类型转换规则&#xff0c;即内置类型转换&#xff08;Implicit Type Conversion&#xff09;&#xff0c;也称为类型提升&#xff08;Type Promotion&#xff09;或类型转换&#xff08;Type Casting&#xff09;。 内置类型转换…

【C++】——string类的介绍及模拟实现

文章目录 1. 前言2. string类的常用接口2.1 string类对象的常见构造2.2 string类对象的容量操作2.3 string类对象的访问及遍历操作2.4 string类对象的修改操作2.5 string类非成员函数2.6 string四种迭代器类型2.7 string类的insert和erase函数 3. 浅拷贝和深拷贝4. string类模拟…

算法Day15 | 层序遍历,102,107,199,637,429,515,116,117,104,111,226,101

Day15 层序遍历102.二叉树的层序遍历107.二叉树的层次遍历 II199.二叉树的右视图637.二叉树的层平均值429.N叉树的层序遍历515.在每个树行中找最大值116.填充每个节点的下一个右侧节点指针117.填充每个节点的下一个右侧节点指针II104.二叉树的最大深度111.二叉树的最小深度 226…

新手使用php7的加密方法来保护代码的安全性

网站、APP等应用的安全性也越来越重要。在开发应用的过程中&#xff0c;为了保护代码不被恶意攻击者窃取和篡改&#xff0c;代码加密就显得非常有必要了。本文将介绍如何使用php7的加密方法来保护代码的安全性。 一、什么是代码加密&#xff1f; 代码加密是将代码进行转码、混…

Adapt Learning使用教程(Adapt Framework/Adapt Authoring)(二)

此文章在上一章的环境配置下操作的&#xff0c;如果还没配置参考我的上一篇文章&#xff1a;Adapt Learning使用教程&#xff08;Adapt Framework/Adapt Authoring&#xff09;&#xff08;一&#xff09; 。环境配置好了之后&#xff0c;就该从GitHub上拉取代码啦&#xff0c…

Centos8下源码编译安装运行Primihub

参考文献 PrimiHub 本地编译启动How to install Bazel on CentOS 8 Linux or Redhat 8/7 编译启动步骤 由于历史原因&#xff0c;服务器是Centos8操作系统&#xff0c;所以源码编译异常的麻烦。特此记录如下。 采用源码编译方式可以在一步步的运行过程中对整个流程进行深刻…

IDEA 2022.2 安装以及自定义优化

IDEA2022.2 安装以及自定义优化 文章目录 IDEA2022.2 安装以及自定义优化安装图解获取激活码自定义优化文件编码设置设置类文档注释和方式注释模板方法分割线 常用插件离线安装 安装图解 静默卸载&#xff08;旧版本的设置和配置将不会被删除&#xff09; 获取激活码 略…

今天面试招了个20K的人,从腾讯出来的果然都有两把刷子···

现在找个会自动化测试的人真是难呀&#xff0c;10个里面有8个写了会自动化&#xff0c;但一问就是三不知 公司前段时间缺人&#xff0c;也面了不少测试&#xff0c;前面一开始瞄准的就是中级的水准&#xff0c;也没指望来大牛&#xff0c;提供的薪资在15-20k&#xff0c;面试的…

电源原理分析、波形分析、应力计算、回路布局

1、Flyback变换器工作模态分析&#xff1b; 2、Flyback关键波形分析&#xff1b; 3、RCD吸收电路设计及开关管应力&#xff1b; 4、从噪音回路看布线要点。 5、基于实际项目&#xff0c;原创反激开关电源视频教程曝光 Flyback 变换器模态分析 ​ ON&#xff1a;开关管导通&…

C++条件变量condition_variable

一、问题 假设没有条件变量&#xff0c;对于一个生产者消费者问题&#xff0c;消费线程在得知队列中没有产品时&#xff0c;将阻塞自己。生产者线程可以给队列中放入产品&#xff0c;但是没有办法激活消费者线程&#xff0c;而消费者线程处于阻塞状态也没有办法自己激活自己。…