当前位置: 首页 > news >正文

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][0n]表示可能的答案,每次进行暴力搜索,如果某一次枚举的时候搜索成功,那么此时枚举的次数就是最小的操作次数。这就是IDIDID算法(IterativeDeepeningIterative DeepeningIterativeDeepening迭代深搜)。因为直接搜索的话,我们每次需要枚举区间以及移动的位置,那么复杂度会达到(n3)depth(n ^3)^{depth}(n3)depth带入最大值999的话算出来的值接近6×10256\times 10^{25}6×1025很明显会超时。
那么我们需要使用剪枝,如何进行剪枝呢?由于数字都是1−n1-n1n的,那么我们可以记录每个数字的后一个数字不正确的个数即计算有多少个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(maxDepthnowDepth)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 迭代加深搜剪枝

题目链接&#xff1a;Editing a Book 题目描述&#xff1a; 给定nnn个(1<n<10)1<n<10)1<n<10)数字&#xff0c;数字分别是1,2,3,...,n1, 2, 3, ...,n1,2,3,...,n&#xff0c;但是顺序是打乱的&#xff0c;你可以选择一个索引区间的数字进行剪切操作。问最少进…...

第一章:unity性能优化之内存优化

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

2023年家族办公室研究报告

第一章 概况 家族办公室最早起源于古罗马时期的大“Domus”&#xff08;家族主管&#xff09;以及中世纪时期的大“Domo”&#xff08;总管家&#xff09;。现代意义上的家族办公室出现于19世纪中叶&#xff0c;一些抓住产业革命机会的大亨将金融专家、法律专家和财务专家集合…...

Typescript快速入门

Typescript快速入门第一章 快速入门0、TypeScript简介1、TypeScript 开发环境搭建2、基本类型3、编译选项4、webpack5、Babel第二章&#xff1a;面向对象0、面向对象简介1、类&#xff08;class&#xff09;2、面向对象的特点3、接口&#xff08;Interface&#xff09;4、泛型&…...

如何激励你的内容团队产出更好的创意

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

机械设备管理软件如何选择?机械设备管理软件哪家好?

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

深入浅出带你学习shiro-550漏洞

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

项目(今日指数之环境搭建)

一 项目架构1.1 今日指数技术选型【1】前端技术【2】后端技术栈【3】整体概览1.2 核心业务介绍【1】业务结构预览【2】业务结构预览1.定时任务调度服务XXL-JOB通过RestTemplate多线程动态拉去股票接口数据&#xff0c;刷入数据库&#xff1b; 2.国内指数服务 3.板块指数服务 4.…...

PCL 基于投影点密度的建筑物立面提取

目录 一、算法原理1、投影密度理论及方法2、参考文献二、代码实现三、结果展示一、算法原理 1、投影密度理论及方法 将3维坐标点直接垂直投影到水平面上或者将 Z Z Z 值取任意常数,统计和计算水平面任意位置处所含投影点的个数记为...

DDD 参考工程架构

1 背景 不同团队落地DDD所采取的应用架构风格可能不同&#xff0c;并没有统一的、标准的DDD工程架构。有些团队可能遵循经典的DDD四层架构&#xff0c;或改进的DDD四层架构&#xff0c;有些团队可能综合考虑分层架构、整洁架构、六边形架构等多种架构风格&#xff0c;有些在实…...

重建,是2023年的关键词

作者&#xff1a;俞敏洪 来源&#xff1a;老俞闲话&#xff08;ID&#xff1a;laoyuxianhua&#xff09; 01 重建&#xff0c;是2023年的关键词 1.重建&#xff0c;是2023年的关键词 2023年&#xff0c;以一种奇特的方式来临。 之所以说奇特&#xff0c;是因为我们谁都没有…...

动手写操作系统-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,我的自动化测试心路历程

我希望我的故事能够激励现在的软件测试人&#xff0c;尤其是还坚持在做“点点点”的测试人。 你可能会有疑问&#xff1a;“我也能做到这一点的可能性有多大&#xff1f;”因此&#xff0c;我会尽量把自己做决定和思考的过程讲得更具体一些&#xff0c;并尽量体现更多细节。 …...

JAVA八股、JAVA面经

还有三天面一个JAVA软件开发岗&#xff0c;之前完全没学过JAVA&#xff0c;整理一些面经...... 大佬整理的&#xff1a;Java面试必备八股文_-半度的博客-CSDN博客 另JAVA学习资料&#xff1a;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)))]minG​maxD​V(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&#xff0c;并设置为开机启动 systemctl start postfixsystemctl enable postfix3.防火墙和selinux的设置 setenforce 0systemctl stop fire…...

山洪灾害监测预警平台 山洪灾害监测预警系统解决方案 以人为本 科学防御

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

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系统是一个文件系统&#xff0c;它的文件系统就类似windows系统下的磁盘文件系统。 我们连接上一台linux系统的服务器。 输入命令 &#xff1a; ls / 我们可以看到 linux系统的根目录下有这些目录 bin boot data dev etc hbr home lib lib64 lostfoun…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

基于ASP.NET+ SQL Server实现(Web)医院信息管理系统

医院信息管理系统 1. 课程设计内容 在 visual studio 2017 平台上&#xff0c;开发一个“医院信息管理系统”Web 程序。 2. 课程设计目的 综合运用 c#.net 知识&#xff0c;在 vs 2017 平台上&#xff0c;进行 ASP.NET 应用程序和简易网站的开发&#xff1b;初步熟悉开发一…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

Swagger和OpenApi的前世今生

Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章&#xff0c;二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑&#xff1a; &#x1f504; 一、起源与初创期&#xff1a;Swagger的诞生&#xff08;2010-2014&#xff09; 核心…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...

【前端异常】JavaScript错误处理:分析 Uncaught (in promise) error

在前端开发中&#xff0c;JavaScript 异常是不可避免的。随着现代前端应用越来越多地使用异步操作&#xff08;如 Promise、async/await 等&#xff09;&#xff0c;开发者常常会遇到 Uncaught (in promise) error 错误。这个错误是由于未正确处理 Promise 的拒绝&#xff08;r…...