Editing a Book UVA – 11212 IDA*

You havenequal-length paragraphs numbered 1 ton. Now you want to arrange them in the orderof 1;2;:::;n. With the help of a clipboard, you can easily do this: Ctrl-X (cut) and Ctrl-V (paste)several times. You cannot cut twice before pasting, but you can cut several contiguous paragraphs atthe same time – they’ll be pasted in order.For example, in order to makef2, 4, 1, 5, 3, 6g, you can cut 1 and paste before 2, then cut 3 andpaste before 4. As another example, one copy and paste is enough forf3, 4, 5, 1, 2g. There are twoways to do so: cutf3, 4, 5gand paste afterf1, 2g, or cutf1, 2gand paste beforef3, 4, 5g.InputThe input consists of at most 20 test cases. Each case begins with a line containing a single integern(1<n<10), thenumber of paragraphs. The next line contains a permutation of 1;2;3;:::;n. Thelast case is followed by a single zero, which should not be processed.OutputFor each test case, print the case number and the minimal number of cut/paste operations.Sample Input62 4 1 5 3 653 4 5 1 20Sample OutputCase 1: 2Case 2: 1

/**
题目：Editing a Book UVA - 11212
链接：https://vjudge.net/problem/UVA-11212
题意：lrjP208.
思路：启发函数：当前已经操作的步数d，限制的步数maxd，后继不相同的个数x。
由于每一步最多使x减少3，所以如果3*d+x>maxd*3;那么肯定不行。如果通过位置不同的个数作为启发，是不行的，无法判断。如果是每个数的后继不同的数有多少个。那么可以推算出每一步操作后，最多减少3个不同的后继。最终结果所有后继都满足。即a[i] = a[i-1]+1;具体看lrj算法竞赛入门经典P209；*/#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod=1e9+;
const int maxn=1e2+;
const double eps = 1e-;
int a[], n;
int getDif()///获得后继不合法数.
{
    int cnt = ;
    for(int i = ; i <= n; i++){
        if(a[i]!=a[i-]+){
            cnt++;
        }
    }
    return cnt;
}
int temp[];
void Move(int *temp,int *a,int L,int R,int LL,int RR)
{
    int now = L;
    for(int i = LL; i <= RR; i++){
        a[now++] = temp[i];
    }
    for(int i = L; i <= R; i++){
        a[now++] = temp[i];
    }
}
bool dfs(int d,int maxd)
{
    if(*d+getDif()>*maxd) return false;
    if(getDif()==) return true;
    int odd[];
    memcpy(odd,a,sizeof(int)*(n+));
    ///如果[L,R]是连续的，那么不需要剪切。
    for(int i = ; i <= n; i++){
        for(int j = i; j <= n; j++){
            for(int k = j+; k <= n; k++){///每次交换[i,j],[j+1,k]；每次交换相邻的两段区间。
                Move(odd,a,i,j,j+,k);
                if(dfs(d+,maxd)) return true;
                memcpy(a,odd,sizeof(int)*(n+));///保证每一次操作后，把a复原。
            }
        }
    }
    return false;
}
int main()
{
    int cas = ;
    while(scanf("%d",&n)==)
    {
        if(n==) break;
        for(int i = ; i <= n; i++) scanf("%d",&a[i]);
        for(int maxd = ; ; maxd++){
            if(dfs(, maxd)){
                printf("Case %d: %d\n",cas++,maxd); break;
            }
        }
    }
    return ;
}