IDA星其实就是迭代深搜版的A星，每个状态下，如果当前深度加上估计函数的值大于当前限制的深度，那么就返回。这样相比A星的编程难度要小一点，在一些地方效率高于A星。

例题：排书

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define per(i,j,k) for(int i=j;i>=k;i--)
typedef long long ll;
using namespace std;

template<typename T>void in(T &x) {
    char ch = getchar();bool flag = 0;x = 0;
    while(ch < '0' || ch > '9') flag |= (ch == '-'), ch = getchar();
    while(ch <= '9' && ch >= '0') x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
    if(flag) x = -x;return ;
}

int n,limit ;

bool IDA_Star(int dep,int a[16]){
    int tot=0;
    if(dep>limit) return 0;
    rep(i,1,n-1)
        if(a[i+1]!=a[i]+1) tot++;
    if(a[n]!=n) tot++;
//  printf("%d\n%tot",dep,tot);
    if(!tot) return 1;
    int b[16];
    tot=(tot-1)/3+1;
    if(dep+tot>limit) return 0;
    rep(i,1,n-1){
        rep(j,1,n-i+1)   //选择位置的开头 
            rep(k,1,j-1){   //只能往前放 
                int num=0;
                rep(q,1,k-1) b[++num]=a[q];
                rep(q,j,j+i-1) b[++num]=a[q];
                rep(q,k,j-1) b[++num]=a[q];
                rep(q,j+i,n) b[++num]=a[q];
                if(IDA_Star(dep+1,b)) return 1;
            }
    }
    return 0;
}

void solve(){
    in(n);
    int g[16];
    rep(i,1,n) in(g[i]);
    for(limit=0;limit<=4;limit++)
        if(IDA_Star(0,g)) {
            printf("%d\n",limit);
            return ;
        }
    printf("5 or more\n");
}

int main(){
    int T;
    in(T);
    while(T--)solve();
    return 0;
}