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…...

观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...

linux之kylin系统nginx的安装
一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源(HTML/CSS/图片等),响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址,提高安全性 3.负载均衡服务器 支持多种策略分发流量…...
【Linux】C语言执行shell指令
在C语言中执行Shell指令 在C语言中,有几种方法可以执行Shell指令: 1. 使用system()函数 这是最简单的方法,包含在stdlib.h头文件中: #include <stdlib.h>int main() {system("ls -l"); // 执行ls -l命令retu…...

React19源码系列之 事件插件系统
事件类别 事件类型 定义 文档 Event Event 接口表示在 EventTarget 上出现的事件。 Event - Web API | MDN UIEvent UIEvent 接口表示简单的用户界面事件。 UIEvent - Web API | MDN KeyboardEvent KeyboardEvent 对象描述了用户与键盘的交互。 KeyboardEvent - Web…...

【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)
更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现
摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序,以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务,提供稳定高效的数据处理与业务逻辑支持;利用 uniapp 实现跨平台前…...
Linux云原生安全:零信任架构与机密计算
Linux云原生安全:零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言:云原生安全的范式革命 随着云原生技术的普及,安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测,到2025年,零信任架构将成为超…...

现代密码学 | 椭圆曲线密码学—附py代码
Elliptic Curve Cryptography 椭圆曲线密码学(ECC)是一种基于有限域上椭圆曲线数学特性的公钥加密技术。其核心原理涉及椭圆曲线的代数性质、离散对数问题以及有限域上的运算。 椭圆曲线密码学是多种数字签名算法的基础,例如椭圆曲线数字签…...

无人机侦测与反制技术的进展与应用
国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机(无人驾驶飞行器,UAV)技术的快速发展,其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统,无人机的“黑飞”&…...