加了一些注释

c++版本

#include <iostream>
#include <cstring>
using namespace std;

const int N = 15;
int n, q[N], w[5][N];

/*1的后继的意思是，1的后面必须是2，那么1的后继是非2的话，这个后继就是错误的*/
//估价函数的解释：每挪一次会修改三个后继
//tot存的是错误的后继的数量，那么除以3上取整就相当于最少还需要多少层dfs
int f()
{
    int tot = 0;
    for(int i = 0; i + 1 < n; i++)
        if(q[i] + 1 != q[i + 1])
            tot++;
    return (tot + 2) / 3;
}

bool dfs(int u, int depth)
{
    //如果当前的层数加最少的层数大于最多的层数，方案无解返回false
    if(u + f() > depth) return false;
    //如果估价函数==0，那么tot==0，则是错误后继为0，那么这就是答案
    if(!f()) return true;
    for(int len = 1; len <= n; len++)
        for(int l = 0; l + len - 1 < n; l++)
        {
            int r = l + len - 1;
            //往前挪和往后挪是对称的，所以只需要枚举往后挪的情况
            for(int k = r + 1; k < n; k++)
            {
                memcpy(w[u], q, sizeof q);
                int y = l;
                //首先要把这个区间的后面的数挪上来
                //有挪1个，挪2个……等等选择，挪1个相当于插入到r + 1的位置
                for(int x = r + 1; x <= k; x++, y++) q[y] = w[u][x];
                //插入
                for(int x = l; x <= r; x++, y++) q[y] = w[u][x];
                if(dfs(u + 1, depth)) return true;
                memcpy(q, w[u], sizeof w[u]);
            }
        }
    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;
}