题意
你有一篇由n(2<=n<=9)个自然段组成的文章，希望将它们排列成1,2，···，n。可以用剪切和粘贴来完成任务。每次可以剪切一段连续的自然段，粘贴时按照顺序粘贴。注意剪贴板只有一个，所以不能连续剪切两次，只能剪切和粘贴交替。
分析
鄙人真的不擅长搜索，花了两天时间做完搜索专题的作业，然后被这一道题卡了一天，结果今下午的比赛又是搜索专题，我又不知道得补到啥时候···难受！
这个题是比较显然的IDA*，主要是估值函数h()的计算。如果当前有res个数字的位置不正确，而每次剪切h()最多可以减少3.所以当h()>cur的时候，return false。
然后还加了一个优化（不影响ac，但是会快不少），就是如果存在连续的一段，在cut的时候不把他们拆开。
下面是ac的代码
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std;
const int maxn=;
int a[maxn],b[maxn];
int n,kase;
bool judge(){
for(int i=;i<=n;i++){
if(b[i]!=i)
return false;
}
return true;
}
void ope(int from,int len,int to){//将从from开始，长度为len的一段序列，复制到to位置，然后to位置到from-1位置原来的元素后延
int c[maxn];
for(int i=from,j=;j<=len;i++,j++)
c[j]=b[i];
if(from>to){
for(int i=from-;i>=to;i--)
b[i+len]=b[i];
for(int i=to,j=;j<=len;i++,j++)
b[i]=c[j];
}else if(from<to){
for(int i=from+len;i<=to;i++)
b[i-len]=b[i];
for(int i=to,j=len;j>=;i--,j--)
b[i]=c[j];
}
}
void recover(int from,int len, int to){
if(from<to){
ope(to-len+,len,from);
}else if(to<from){
ope(to,len,from+len-);
}
} bool opeti(int F,int L,int to){
if(F!=)
if(b[F-]+==b[F])
return false;
if(F+L-!=n)
if(b[F+L-]+==b[F+L])
return false;
return true;
}
int h(){
int res=;
for(int i=;i<n;i++)
if(b[i]+!=b[i+])res++;
if(b[n]!=n)res++;
return res;
} bool dfs(int cur){
if(cur==){
if(judge())
return true;
return false;
}
if(h()>*cur)return false;
for(int F=;F<=n;F++){
for(int L=;L<=n-F+;L++){
for(int to=;to<=n;to++){
if(!opeti(F,L,to))continue;
if(to==F)continue;
if(to>F&&to<=F+L-)continue;
if(to<F&&to>=F-L+)continue;
ope(F,L,to);
if(dfs(cur-))
return true;
recover(F,L,to);
}
}
}
return false;
}
int main(){
// freopen("out.txt","w",stdout);
kase=;
while(scanf("%d",&n)!=EOF&&n){
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=n;i++)
b[i]=a[i];
int ans=;
for(int maxd=;;maxd++){
if(dfs(maxd)){
ans=maxd;
break;
}
}
printf("Case %d: %d\n",++kase,ans);
}
return ;
}