莫欺少年穷，修魔之旅在这开始—>算法提高课题解

IDA*+迭代加深

思路：

1. 如果真实值 + 估价值 > 当前最大深度，直接 return
2. 估价函数：(后继数 + 2) / 3
3. 做法：枚举每一种长度，对于每一种长度，都有 n - len + 1 种选择，对于每一种选择又有 n - len 种插法
4. 不要忘了恢复现场哟！

#include<bits/stdc++.h>

using namespace std;

const int N = 15;

int n;
int q[N];
int w[5][N];

//错误的后继数的最少还要执行多少次，一次搞对三个后继数
int f()
{
    int cnt=0;
    for(int i=0;i<n-1;i++)
        if(q[i+1]!=q[i]+1)
            cnt++;

    return (cnt+2)/3;
}

//是否存在错误的后继数
bool check()
{
    for(int i=0;i<n-1;i++)
        if(q[i+1]!=q[i]+1)
            return false;

    return true;
}

bool dfs(int u,int depth)
{
    //当前层+最少还要执行的估价层数
    if(u+f()>depth) return false;

    //判断是否还有后继数
    if(check()) return true;

    //枚举所有长度
    for(int len=1;len<=n;len++)

        //枚举每一种长度的所有选择
        for(int l=0;l<=n-len+1;l++)
        {
            int r=l+len-1;

            //枚举每一种选择可以放在哪里
            for(int k=r+1;k<=n;k++)
            {
                //提前备份
                memcpy(w[u],q,sizeof q);

                int x,y;

                //把后一段移到前面去
                for(x=r+1,y=l;x<=k;x++,y++) q[y]=w[u][x];

                //把前一段移到后面去
                for(x=l;x<=r;x++,y++) q[y]=w[u][x];

                //搞下一次操作
                if(dfs(u+1,depth)) return true;

                //恢复现场
                memcpy(q,w[u],sizeof q);
            }
        }

    return false;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;

        for(int i=0;i<n;i++) cin>>q[i];

        int depth=0;
        while(depth<5&&!dfs(0,depth)) depth++;

        if(depth==5) cout<<"5 or more"<<endl;
        else cout<<depth<<endl;
    }

    return 0;
}