Editing a Book UVA - 11212

题意：有一篇由n(2<=n<=9)个自然段组成的文章，希望将它们排列成1,2......n。可以用剪切和粘贴快捷键来完成任务。每次可以剪切一段连续的自然段，粘贴时按照顺序粘贴。注意粘贴板只有一个，所以不能连续剪切两次，只能剪切和粘贴交替。例如为了将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前。

思路：IDA*算法，，考虑后即不正确的数字个数h，可以证明每次剪切时h最多减少3（证明过程详见紫书209页），因此当3*d + h > 3 * maxd时可以剪枝，其中d为当前深度，maxd为深度限制。这里学习了模拟复制粘贴的过程。

#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn = 10;
int n,maxd,a[maxn];
//这里不正确的数字是指不连续的数字有几段
int h()
{
    int num = 0;
    for(int i = 0;i < n - 1;i++)
    {
        if(a[i] + 1 != a[i + 1])
        {
            num++;
        }
    }
    if(a[n - 1] != n) num++;
    return num;
}
int dfs(int d)
{
    int cnt = h();
    if(d * 3 + cnt > maxd * 3) return false;
    if(cnt == 0)  return true;
    int b[10],c[10];
    memcpy(b,a,sizeof(a));
    for(int i=0;i<n;i++)
    {
        for(int j=i;j<n;j++)
        {
            int cnt1=j-i+1,cnt2=n-cnt1;
            memcpy(c,b,sizeof(int)*i);
            memcpy(c+i,b+j+1,sizeof(int)*(n-j));
            for(int k=0;k<=cnt2;k++)
            {
                if(i==k) continue;
                memcpy(a,c,sizeof(int)*k);
                memcpy(a+k,b+i,sizeof(int)*cnt1);
                memcpy(a+k+cnt1,c+k,sizeof(int)*(n-cnt1-k));
                if(dfs(d+1)) return true;
            }
        }
    }
    memcpy(a,b,sizeof(a));
    return false;
}
int main()
{
    int num = 1;
    while(scanf("%d",&n) && n)
    {
        for(int i = 0;i < n;i++)
        {
            scanf("%d ",&a[i]);
        }
        printf("Case %d: ",num++);
        for(maxd = 0;maxd <= n;maxd++)
        {
            if(dfs(0))
            {
                printf("%d\n",maxd);
                break;
            }
        }
    }
    return 0;
}