题意
你有一篇由n(2<=n<=9)个自然段组成的文章，希望将它们排列成1,2，···，n。可以用剪切和粘贴来完成任务。每次可以剪切一段连续的自然段，粘贴时按照顺序粘贴。注意剪贴板只有一个，所以不能连续剪切两次，只能剪切和粘贴交替。
分析
鄙人真的不擅长搜索，花了两天时间做完搜索专题的作业，然后被这一道题卡了一天，结果今下午的比赛又是搜索专题，我又不知道得补到啥时候···难受！
这个题是比较显然的IDA*，主要是估值函数h()的计算。如果当前有res个数字的位置不正确，而每次剪切h()最多可以减少3.所以当h()>cur的时候，return false。
然后还加了一个优化（不影响ac，但是会快不少），就是如果存在连续的一段，在cut的时候不把他们拆开。
下面是ac的代码
1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 #include <algorithm> 5 6 using namespace std; 7 const int maxn=15; 8 int a[maxn],b[maxn]; 9 int n,kase; 10 bool judge(){ 11 for(int i=1;i<=n;i++){ 12 if(b[i]!=i) 13 return false; 14 } 15 return true; 16 } 17 void ope(int from,int len,int to){//将从from开始，长度为len的一段序列，复制到to位置，然后to位置到from-1位置原来的元素后延 18 int c[maxn]; 19 for(int i=from,j=1;j<=len;i++,j++) 20 c[j]=b[i]; 21 if(from>to){ 22 for(int i=from-1;i>=to;i--) 23 b[i+len]=b[i]; 24 for(int i=to,j=1;j<=len;i++,j++) 25 b[i]=c[j]; 26 }else if(from<to){ 27 for(int i=from+len;i<=to;i++) 28 b[i-len]=b[i]; 29 for(int i=to,j=len;j>=1;i--,j--) 30 b[i]=c[j]; 31 } 32 } 33 void recover(int from,int len, int to){ 34 if(from<to){ 35 ope(to-len+1,len,from); 36 }else if(to<from){ 37 ope(to,len,from+len-1); 38 } 39 } 40 41 bool opeti(int F,int L,int to){ 42 if(F!=1) 43 if(b[F-1]+1==b[F]) 44 return false; 45 if(F+L-1!=n) 46 if(b[F+L-1]+1==b[F+L]) 47 return false; 48 return true; 49 } 50 int h(){ 51 int res=0; 52 for(int i=1;i<n;i++) 53 if(b[i]+1!=b[i+1])res++; 54 if(b[n]!=n)res++; 55 return res; 56 } 57 58 bool dfs(int cur){ 59 if(cur==0){ 60 if(judge()) 61 return true; 62 return false; 63 } 64 if(h()>3*cur)return false; 65 for(int F=1;F<=n;F++){ 66 for(int L=1;L<=n-F+1;L++){ 67 for(int to=1;to<=n;to++){ 68 if(!opeti(F,L,to))continue; 69 if(to==F)continue; 70 if(to>F&&to<=F+L-1)continue; 71 if(to<F&&to>=F-L+1)continue; 72 ope(F,L,to); 73 if(dfs(cur-1)) 74 return true; 75 recover(F,L,to); 76 } 77 } 78 } 79 return false; 80 } 81 int main(){ 82 // freopen("out.txt","w",stdout); 83 kase=0; 84 while(scanf("%d",&n)!=EOF&&n){ 85 for(int i=1;i<=n;i++) 86 scanf("%d",&a[i]); 87 for(int i=1;i<=n;i++) 88 b[i]=a[i]; 89 int ans=0; 90 for(int maxd=0;;maxd++){ 91 if(dfs(maxd)){ 92 ans=maxd; 93 break; 94 } 95 } 96 printf("Case %d: %d ",++kase,ans); 97 } 98 return 0; 99 }