UVA11212 Editing a Book

一、题目内容

【题目描述】

你有一篇n个自然段组成的文章，希望将它们排列成1，2，…，n。可以用Ctrl+X（剪切）和Ctrl+V（粘贴）快捷键来完成任务。每次可以剪切一段连续的自然段，粘贴时按照顺序粘贴。注意，剪贴板只有一个，所以不能连续剪切两次，只能剪切和粘贴交替。例如，为了将{2，4，1，5，3，6}变为升序，可以剪切1将其放到2前，然后剪切3将其放到4前。再如，排列{3，4，5，1，2}，只需一次剪切和一次粘贴即可——将{3，4，5}放在{1，2}后，或者将{1，2}放在{3，4，5}前。

【输入格式】

多组输入数据，对于每组输入数据
第一行一个整数n (1 < n < 10)
第二行n个整数
当n=0结束

【输出格式】

对于第i组输入数据，输出:
Case i: ans
ans 为最少的操作次数
每组输出用占一行

【输入样例】

6
2 4 1 5 3 6
5
3 4 5 1 2
0

【输出样例】

Case 1: 2
Case 2: 1

【测试网站】

uva11212

二、题目分析

本题利用迭代加深搜索，也是一道典型的状态空间搜索问题，状态就是1~n的排列，初始状态是输入，终止状态是1,2,……n。由于n≤9,排列最多有9！=362880个，但由于每个状态的后继状态比较多，因此仍有TLE的危险。很显然，最坏的情况是需要n-1次剪切，搜索层数不多，但每一层的状态数目又非常庞大，适宜使用IDA。本题如果利用迭代加深搜索，可以发现做多只需要8步，关键在于如何有效地剪枝。考虑后继不正确的数字的个数h，可以证明每次剪切时h最多减少3（因为一次剪切最多只会改变3个数字的后继，若剪切后这3个数字的后继都正确，则h最多减少了3），因此当h>3(maxd-d)时剪枝即可
减枝分析（也叫做启发函数）：
当改变一个区间的位置，最多会改变3个数的位置的正确性。
比如 1,2,3,4,5,6.序列，把2,3移动到6后面，那么1的后面变成了5, 而 6的后面编程了2,而3的后面变成 空了，同样，设当前有四个数字 a b c d ，如果把b移到c后面，则改变了a、b、c三个数的后继，所以最多会改变3个数的位置的正确性。
也就是说，对于这道题，如果遍历到了一个深度，（还能遍历的深度 - 当前深度） x 3　< 不正确数字的个数，那么就没有必要继续遍历了，因为往后就是全把这些数字该对了也无法达到理想状态。
知道这个之后时间复杂度的问题就得到解决了，只需要每次枚举该步的所有移动就可以了。
搜索：截取 [i, j] 插入剩余序列的第k个数字前

三、代码示例

#include <bits/stdc++.h>

using namespace std;
const int maxn = 10;

int n, Case=0;
int a[maxn];

int is_sort()
{
  int res = 0;
  for(int i = 0; i < n-1; i++) if(a[i]+1 != a[i+1]) res++;
  if(a[n-1] != n) res++;
  return res;
}

bool dfs(int maxd,int d)
{
  int h = is_sort();
  if(h == 0) return true;
  if(h > (maxd-d)*3) return false;

  int b[maxn],old[maxn];
  memcpy(old,a,sizeof(old));
  for(int i = 0; i < n; i++)
   for(int j = i; j < n; j++)
    {
      int tot = 0;
      for(int k = 0; k < i; k++) b[tot++] = old[k];
      for(int k = j+1; k < n; k++) b[tot++] = old[k];
      for(int k = 0; k <= tot; k++)
      {
        int tot1 = 0;
        for(int v = 0; v < k; v++) a[tot1++] = b[v];
        for(int v = i; v <= j; v++) a[tot1++] = old[v];
        for(int v = k; v < tot; v++) a[tot1++] = b[v];
        if(dfs(maxd,d+1)) return true;
      }
    }
    return false;
}

int solve()
{
  for(int i = 1; i < n-1; i++)
    if(dfs(i,0)) return i;
  return n-1;
}

int main()
{
  while(scanf("%d",&n) && n)
  {
    for(int i = 0; i < n; i++) scanf("%d",&a[i]);
    if(is_sort() == 0) {printf("Case %d: %d\n",++Case,0);continue;}
    printf("Case %d: %d\n",++Case,solve());
  }
  return 0;
}