HDU1685Booksort（IDA* 搜索）

本文主要是介绍HDU1685Booksort（IDA* 搜索），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：有一段书编号1-n，初始状态是乱序的，问是否可以再4步操作内让他有序，每次的操作可以任取一段连续的书插在任一位置。
黑书169上的例题，第一次接触IDA*，慢慢理解

#include<iostream>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<queue>
#include<set>
#include<stack>
#define cl(a,b) memset(a,b,sizeof(a));
#define LL long long
#define P pair<int,int>
#define X first
#define Y second
#define out(x) cout<<x<<endl;
using namespace std;
const int maxn=20;
const int inf=9999999;int n;
int a[maxn];
bool pan(){for(int i=1;i<=n;i++){if(a[i]!=i)return false;}return true;
}
int limit;///深度限制，对于f(s)=g(s)+h(s)>limit直接跳过，s某一表示状态
int h(){///估价函数，详细见黑书169int t=0;for(int i=0;i<=n;i++){if(a[i]+1!=a[i+1])t++;}return t;
}
bool flag;
void IDA_start(int dept){if(pan()||flag){flag=true;return ;}if(dept*3+h()>limit*3){return ;///启发函数，剪枝,当前的启发函数的值大于深度限制，结束}int tmp[maxn];for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){for(int k=j+1;k<=n;k++){///选择[i,j]的书插入到[j+1,k]的某一位置memcpy(tmp,a,sizeof(tmp));for(int p=j+1;p<=k;p++){a[p-j-1+i]=tmp[p];}for(int p=i;p<=j;p++){a[p+k-j]=tmp[p];}IDA_start(dept+1);memcpy(a,tmp,sizeof(tmp));}for(int k=1;k<=i-1;k++){///选择[i,j]的书插入到[1,i-1]的某一位置memcpy(tmp,a,sizeof(tmp));for(int p=k;p<=i-1;p++){a[p+j-i+1]=tmp[p];}for(int p=i;p<=j;p++){a[p-i+k]=tmp[p];}IDA_start(dept+1);memcpy(a,tmp,sizeof(tmp));}}}
}int main(){int T;scanf("%d",&T);while(T--){scanf("%d",&n);bool ok=true;for(int i=1;i<=n;i++){scanf("%d",&a[i]);if(a[i]!=i)ok=false;}if(ok){puts("0");continue;}a[0]=0;a[n+1]=n+1;limit=1;flag=false;while(true){IDA_start(0);limit++;if(flag||limit>=5){break;}}if(flag){printf("%d\n",limit-1);}else {printf("5 or more\n");}}return 0;
}