算法：IDA*

使用了更直观的方法枚举当前状态的分支

将第i~j(区间左闭右开)本书放到第k本之后相当于i~j与j~k两个区间交换了位置
这里可以不使用额外的空间存储当前区间，有一种O(n)时间,O(1)空间交换相邻序列的算法：
如 abc , def ==》 def , abc
可以先将abc和def分别倒置为cba , fed 再将整个序列倒置就有 def , abc
注意恢复现场时前后两个区间的长度经过交换变成了k-j和j-i，因此恢复时应该写成op(i,i+k-j,k)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N = 16;
int a[N],n;

int f()
{
    int res = 0;
    for(int i = 0 ; i < n-1 ; i ++)
        if(a[i]+1!=a[i+1]) res++;
    return (res+2)/3;
}

void op(int i, int j , int k)
{
    reverse(a+i,a+j);
    reverse(a+j,a+k);
    reverse(a+i,a+k);
}

bool dfs(int u,int max_depth)
{
    int h = f();
    if(!h) return true;
    if(u+h>max_depth) return false;


    for(int i = 0 ; i < n-1 ; i ++)
    {
        for(int j = i + 1 ; j < n ; j ++)
        {
            for(int k = j+1 ; k <= n ; k ++)
            {
                op(i,j,k);
                if(dfs(u+1,max_depth)) return true;
                op(i,i+k-j,k);
            }
        }
    }
    return false;
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        cin >> n;
        for(int i = 0 ; i < n ; i ++)
          cin >> a[i];
        int d = 0;
        while(d<5&&!dfs(0,d)) d++;
        if(d>=5) puts("5 or more");
        else cout << d << endl;
    }
}