UVa 11212 Editing a Book 编辑书稿 IDA* Iterative Deepening A Star 迭代加深搜剪枝
题目链接:Editing a Book
题目描述:
给定nnn个(1<n<10)1<n<10)1<n<10)数字,数字分别是1,2,3,...,n1, 2, 3, ...,n1,2,3,...,n,但是顺序是打乱的,你可以选择一个索引区间的数字进行剪切操作。问最少进行多少次剪切可以让这nnn个数字变成升序。
例如[1,2,4,3][1, 2, 4, 3][1,2,4,3]你可以选择剪切333然后在444的前面进行粘贴操作,那么该操作算一次剪切操作序列变得升序。
题解:
对于一个含有nnn个数字的序列,要想让他变为升序,最多只需要进行nnn次剪切操作一定能让序列升序(即每次都选择未剪切过的最大的数字剪切到开头,最多进行nnn次操作,该序列一定变为有序)。那么我们可以依次枚举[0−n][0-n][0−n]表示可能的答案,每次进行暴力搜索,如果某一次枚举的时候搜索成功,那么此时枚举的次数就是最小的操作次数。这就是IDIDID算法(IterativeDeepeningIterative DeepeningIterativeDeepening迭代深搜)。因为直接搜索的话,我们每次需要枚举区间以及移动的位置,那么复杂度会达到(n3)depth(n ^3)^{depth}(n3)depth带入最大值999的话算出来的值接近6×10256\times 10^{25}6×1025很明显会超时。
那么我们需要使用剪枝,如何进行剪枝呢?由于数字都是1−n1-n1−n的,那么我们可以记录每个数字的后一个数字不正确的个数即计算有多少个iii满足:a[i]+1]≠a[i+1]a[i] + 1] \ne a[i +1]a[i]+1]=a[i+1],我们将这个数字记为cntcntcnt,我们可以发现我们每一次剪切操作最多让cntcntcnt减少333。从下图我们可以看到如果我们进行一次剪切(下图中是把part c
移到到part b
的前面),后一个数字发生变化的位置有:a
的最后一个元素,c
的最后一个元素,b
的最后一个元素。 也就是说在这种情况想最多只有三个数字的后一个元素会发生改变,当然其他情况也是可以同理推出来的。所以每一次剪切操作最多能够让cntcntcnt减少333,如果剩余的剪切操作在最优的情况下不能让cntcntcnt小于000,那么此时就应该停止搜索即:(maxDepth−nowDepth)∗3<cnt(maxDepth - nowDepth) * 3 < cnt(maxDepth−nowDepth)∗3<cnt。这也就是AstarA\ starA star算法的思想,三部分合起来就叫做IDA∗IDA*IDA∗。
实际上仅仅有上面的剪枝策略还是容易发生超时。而此时需要利用另外一种“贪心”策略:连续的升序区间不应该被执行剪切操作,也就是说对于一个序列里面类似于[2,3,4,5][2, 3, 4, 5][2,3,4,5]的序列只能作为整体操作,而不应该只剪切其中的一部分。这似乎是显然的。
代码:
#include <bits/stdc++.h>using namespace std;int n, caseID = 1;
vector<int> number;int getCnt()
{int cnt = 0;for (int i = 0; i < n - 1; i++) {if (number[i] + 1 != number[i + 1]) { cnt++; }}return cnt;
}bool dfs(int nowDepth, int maxDepth)
{int cnt = getCnt();if (nowDepth == maxDepth) { return cnt == 0; }if ((maxDepth - nowDepth) * 3 < cnt) { return false; }for (int l = 0; l < n; l++) {if (l - 1 >= 0 && number[l] - 1 == number[l - 1]) { continue; }for (int r = l; r < n; r++) { // 枚举需要移动的区间的左右端点if (r + 1 < n && number[r] + 1 == number[r + 1]) { continue; }for (int k = r + 2; k <= n; k++) { // 枚举将区间移动到k前面vector<int> temp(number);vector<int> worker;for (int i = 0; i <= k - 1; i++) { // [0, k-1]移动if (l <= i && i <= r) { continue; }worker.push_back(number[i]);}for (int i = l; i <= r; i++) { worker.push_back(number[i]); } // [l, r]移动for (int i = k; i < n; i++) { worker.push_back(number[i]); } // 剩下部分移动number.swap(worker);if (dfs(nowDepth + 1, maxDepth)) { return true; };number.swap(temp);}}}return false;
}int main()
{ios::sync_with_stdio(false);while(cin >> n && n != 0) {number.resize(n);for (int i = 0; i < n; i++) { cin >> number[i]; }for (int maxDepth = 0; ; maxDepth++) {if (dfs(0, maxDepth)) {cout << "Case " << caseID << ": " << maxDepth << endl;caseID++;break;}}}return 0;
}
相关文章:

UVa 11212 Editing a Book 编辑书稿 IDA* Iterative Deepening A Star 迭代加深搜剪枝
题目链接:Editing a Book 题目描述: 给定nnn个(1<n<10)1<n<10)1<n<10)数字,数字分别是1,2,3,...,n1, 2, 3, ...,n1,2,3,...,n,但是顺序是打乱的,你可以选择一个索引区间的数字进行剪切操作。问最少进…...

第一章:unity性能优化之内存优化
目录 前言 unity性能优化之内存的优化 一、unity Analysis工具的使用。 二、内存优化方法 1、设置和压缩图片 2、图片格式 3、动画文件 4、模型 5、RenderTexture(RT) 6、分辨率 7、资源的重复利用 8、shader优化 9、对bundle进行良好的管…...

2023年家族办公室研究报告
第一章 概况 家族办公室最早起源于古罗马时期的大“Domus”(家族主管)以及中世纪时期的大“Domo”(总管家)。现代意义上的家族办公室出现于19世纪中叶,一些抓住产业革命机会的大亨将金融专家、法律专家和财务专家集合…...
Typescript快速入门
Typescript快速入门第一章 快速入门0、TypeScript简介1、TypeScript 开发环境搭建2、基本类型3、编译选项4、webpack5、Babel第二章:面向对象0、面向对象简介1、类(class)2、面向对象的特点3、接口(Interface)4、泛型&…...

如何激励你的内容团队产出更好的创意
对于一个品牌而言,如何创造吸引受众并对受众有价值内容是十分关键的。随着市场数字化的推进,优质的创意和内容输出对一个品牌在市场中有着深远的影响。对于很多内容策划和创作者来说,不断地产出高质量有创意的内容是一件非常有挑战性的事情。…...

机械设备管理软件如何选择?机械设备管理软件哪家好?
随着信息化技术的进步与智能制造的发展趋势,很多机械设备制造企业也在一直探寻适合自己的数字化管理转型之路,而企业上ERP管理软件又是实现数字化管理的前提,机械设备管理软件对于企业来说就是关键一环。机械设备管理软件如何选择?…...

深入浅出带你学习shiro-550漏洞
//发点去年存货 前言 apache shiro是一个java安全框架,作用是提供身份验证,Apache Shiro框架提供了一个Rememberme的功能,存储在cookie里面的Key里面,攻击者可以使用Shiro的默认密钥构造恶意序列化对象进行编码来伪造用户的 Cookie…...

项目(今日指数之环境搭建)
一 项目架构1.1 今日指数技术选型【1】前端技术【2】后端技术栈【3】整体概览1.2 核心业务介绍【1】业务结构预览【2】业务结构预览1.定时任务调度服务XXL-JOB通过RestTemplate多线程动态拉去股票接口数据,刷入数据库; 2.国内指数服务 3.板块指数服务 4.…...
PCL 基于投影点密度的建筑物立面提取
目录 一、算法原理1、投影密度理论及方法2、参考文献二、代码实现三、结果展示一、算法原理 1、投影密度理论及方法 将3维坐标点直接垂直投影到水平面上或者将 Z Z Z 值取任意常数,统计和计算水平面任意位置处所含投影点的个数记为...

DDD 参考工程架构
1 背景 不同团队落地DDD所采取的应用架构风格可能不同,并没有统一的、标准的DDD工程架构。有些团队可能遵循经典的DDD四层架构,或改进的DDD四层架构,有些团队可能综合考虑分层架构、整洁架构、六边形架构等多种架构风格,有些在实…...
重建,是2023年的关键词
作者:俞敏洪 来源:老俞闲话(ID:laoyuxianhua) 01 重建,是2023年的关键词 1.重建,是2023年的关键词 2023年,以一种奇特的方式来临。 之所以说奇特,是因为我们谁都没有…...
动手写操作系统-00-环境搭建以及资料收集
文章目录 动手写操作系统内核目标编本教程适合什么样的人?一些简单的要求操作系统的功能环境搭建参考文档:动手写操作系统内核 一直以来想学习linux操作系统,读了很多关于操作系统的书籍,也想自己动手写个OS 目标编 编写一个操作系统内核;能正常的运行自己编写的OS本教程适合…...

【scipy.sparse包】Python稀疏矩阵详解
【scipy.sparse包】Python稀疏矩阵 文章目录【scipy.sparse包】Python稀疏矩阵1. 前言2. 导入包3. 稀疏矩阵总览4. 稀疏矩阵详细介绍4.1 coo_matrix4.2 dok_matrix4.3 lil_matrix4.4 dia_matrix4.5 csc_matrix & csr_matrix4.6 bsr_matrix5. 稀疏矩阵的存取5.1 用save_npz保…...

从写下第1个脚本到年薪30W,我的自动化测试心路历程
我希望我的故事能够激励现在的软件测试人,尤其是还坚持在做“点点点”的测试人。 你可能会有疑问:“我也能做到这一点的可能性有多大?”因此,我会尽量把自己做决定和思考的过程讲得更具体一些,并尽量体现更多细节。 …...

JAVA八股、JAVA面经
还有三天面一个JAVA软件开发岗,之前完全没学过JAVA,整理一些面经...... 大佬整理的:Java面试必备八股文_-半度的博客-CSDN博客 另JAVA学习资料:Java | CS-Notes Java 基础Java 容器Java 并发Java 虚拟机Java IO目录 int和Inte…...

GAN系列基础知识
原始值函数 原始GAN的值函数是 minGmaxDV(D,G)Ex∼pdata(x)[logD(x)]Ez∼pz(z)[log(1−D(G(z)))]min_Gmax_DV(D,G) E_{x \sim p_{data}(x)}[logD(x)]E_{z \sim p_{z}(z)} [log(1-D(G(z)))]minGmaxDV(D,G)Ex∼pdata(x)[logD(x)]Ez∼pz(z)[log(1−D(G(z)))] 其中Ex…...

Linux/CenterOS 7.9配置汉化gitlab服务器
1.安装gitlab的依赖项 yum install -y curl openssh-server openssh-clients postfix cronie policycoreutils-python2.启动postfix,并设置为开机启动 systemctl start postfixsystemctl enable postfix3.防火墙和selinux的设置 setenforce 0systemctl stop fire…...

山洪灾害监测预警平台 山洪灾害监测预警系统解决方案 以人为本 科学防御
平升电子山洪灾害监测预警平台 山洪灾害监测预警系统解决方案,集信息采集、传输、分析和预警等功能于一体,实现预警信息及时、准确地上传下达,提升监测预警能力,使可能受灾区域能够及时采取措施,最大程度减少人员伤亡和…...

The Number Of ThreadPoolExecutor
序言整理下Java 线程池中线程数量如何设置的依据巨人肩膀:https://blog.csdn.net/weilaizhixing007/article/details/125955693https://blog.csdn.net/yuyan_jia/article/details/120298564#:~:text%E4%B8%80%E4%B8%AA%E7%BA%BF%E7%A8%8B%E6%B1%A0%E5%A4%84%E7%90%86%E8%AE%A1,…...

Linux(Linux各目录结构详解)
我们知道Linux系统是一个文件系统,它的文件系统就类似windows系统下的磁盘文件系统。 我们连接上一台linux系统的服务器。 输入命令 : ls / 我们可以看到 linux系统的根目录下有这些目录 bin boot data dev etc hbr home lib lib64 lostfoun…...
React 第五十五节 Router 中 useAsyncError的使用详解
前言 useAsyncError 是 React Router v6.4 引入的一个钩子,用于处理异步操作(如数据加载)中的错误。下面我将详细解释其用途并提供代码示例。 一、useAsyncError 用途 处理异步错误:捕获在 loader 或 action 中发生的异步错误替…...

基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...

dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?
在工业自动化持续演进的今天,通信网络的角色正变得愈发关键。 2025年6月6日,为期三天的华南国际工业博览会在深圳国际会展中心(宝安)圆满落幕。作为国内工业通信领域的技术型企业,光路科技(Fiberroad&…...

保姆级【快数学会Android端“动画“】+ 实现补间动画和逐帧动画!!!
目录 补间动画 1.创建资源文件夹 2.设置文件夹类型 3.创建.xml文件 4.样式设计 5.动画设置 6.动画的实现 内容拓展 7.在原基础上继续添加.xml文件 8.xml代码编写 (1)rotate_anim (2)scale_anim (3)translate_anim 9.MainActivity.java代码汇总 10.效果展示 逐帧…...

门静脉高压——表现
一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构:由肠系膜上静脉和脾静脉汇合构成,是肝脏血液供应的主要来源。淤血后果:门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血,引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...

C#中用于控制自定义特性(Attribute)
我们来详细解释一下 [AttributeUsage(AttributeTargets.Class, AllowMultiple false, Inherited false)] 这个 C# 属性。 在 C# 中,Attribute(特性)是一种用于向程序元素(如类、方法、属性等)添加元数据的机制。Attr…...
[特殊字符] Spring Boot底层原理深度解析与高级面试题精析
一、Spring Boot底层原理详解 Spring Boot的核心设计哲学是约定优于配置和自动装配,通过简化传统Spring应用的初始化和配置流程,显著提升开发效率。其底层原理可拆解为以下核心机制: 自动装配(Auto-Configuration) 核…...

从0开始学习R语言--Day17--Cox回归
Cox回归 在用医疗数据作分析时,最常见的是去预测某类病的患者的死亡率或预测他们的结局。但是我们得到的病人数据,往往会有很多的协变量,即使我们通过计算来减少指标对结果的影响,我们的数据中依然会有很多的协变量,且…...