正如书上所说，本题需要用IDA*算法求解
启发函数是3d+h>3maxd（d为当前操作步骤数，h为当前逆序对数，maxd为当前枚举的最大步骤数）
可见迭代递归的核心思想是枚举ans去dfs是否可行，相反常规搜索是dfs去需找ans。
一开始卡在状态图的转移与回溯上，参考（http://blog.csdn.net/sssogs/article/details/8836606）大神的代码后得到启发，可以将图或是表直接写成结构体或是类跟着递归走（当然，图或是表不能很大，比较大的话应该还是用回溯比较好吧）
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <algorithm>
#define maxn 20
using namespace std;
int maxd,cnt;
class MyClass{
public:
int map[maxn];
int h,n;
void move(int s,int e,int k){
int t[maxn];
for (int i=;i<k;i++){
t[i]=map[i];
}
for (int i=s;i<=e;i++){
t[k+i-s]=map[i];
}
int top=k+e-s;
for (int i=k;i<n;i++){
if (i<s||i>e) t[++top]=map[i];
}
memcpy(map,t,sizeof(t));
}
void move2(int s,int e,int k){
int t[maxn],i,j;
for (i=; i<s; i++)
{
t[i]=map[i];
}
for (j=e+; j<k; j++,i++)
{
t[i]=map[j];
}
for (j=s; j<=e; j++,i++)
{
t[i]=map[j];
}
for (j=k; j<n; j++,i++)
{
t[i]=map[j];
}
memcpy(map,t,sizeof(t));
}
int getH(){
h=;
for (int i=;i<n-;i++)
if (map[i]+!=map[i+]) h++;
if (map[n-]!=n) h++;//经过测试，这一句减掉了60%的搜索量.......之前一直TLE，天呢，又是一下午
return h;
}
bool init(){
cin>>n;
if (n==) return false;
for (int i=;i<n;i++){
cin>>map[i];
}
return true;
}
};
int IDAdfs(int d,MyClass c){
c.getH();
MyClass tc;
cnt++;
if (c.h==) return ;
//if (d==maxd&&c.h>0) return 0;
if (*d+c.h>*maxd) return ;
for (int i=;i<c.n;i++)
for (int j=i;j<c.n;j++){
for (int k=;k<i;k++){
tc=c;
tc.move(i,j,k);
if (IDAdfs(d+,tc)) return ;
}
for (int k=j+; k<c.n; k++)
{
tc=c;
tc.move(i,j,k);
if (IDAdfs(d+,tc) == true)
return true;
}
}
return ;
}
int main()
{
MyClass b;
int prob;
prob=;
while (b.init() == true)
{
cnt=;
for (maxd=; ; maxd++)
{
if (IDAdfs(,b) == true)
break;
}
printf("Case %d: %d\n",prob,maxd);
prob++;
//cout<<cnt<<endl;
}
}