UVA11212 Editing a Book（编辑书稿）

UVA11212 Editing a Book

题目链接

这道题有一定的难度，参考了一些大佬的代码，在这里写一篇题解巩固一下。

问题分析

首先，本题采用IDA*算法求解，参考紫皮书上的解释，这道题启发函数的求解是解题的一个关键。

其次是三个加速的策略： 1.每次只剪切一段连续的数字。 2.假设剪切片段的第一个数字为a，最后一个数字为b，这个片段要么粘贴到a-1下一个位置，要么粘贴到b+1的前一个位置。 3.已经排好序的数字不要分开剪切，始终看做一个整体。 （以上解释纯属搬书，下面结合代码具体分析）

最后，启发函数的求解，设最多剪切maxd次，d是已经剪切的次数，后继不正确的数字还有h个，不难发现，每次剪切最多可以改变3个数字的直接后继。 如下图，把2移到3之后，只有1后继变为3,3后继变为2,2后继变为4. 由此可得当h>3*(maxd-d)时可以剪枝。

代码

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
using namespace std;
int geth(vector& nums)
{
	int cnt = 0;
	for (int i = 1; i  3 * (maxd - d))
		return false;
	for (i = 0; i