算法

(IDA*) $O(560^4)$

先考虑每一步的决策数量：
当抽取长度为 $i$ 的一段时，有 $n - i + 1$ 种抽法，对于每种抽法，有 $n - i$ 种放法。另外，将某一段向前移动，等价于将跳过的那段向后移动，因此每种移动方式被算了两遍，所以每个状态总共的分支数量是：$\sum _{i=1}^n(n-i) * (n - i + 1) / 2 = (15 * 14 + 14 * 13 + … + 2 * 1) / 2 = 560$。

考虑在四步以内解决，最多有 $560^4$ 个状态，会超时。
可以使用双向BFS或者IDA*来优化。

我们用IDA*来解决此题。
估价函数：

• 估价函数需要满足：不大于实际步数
• 在最终状态下，每本书后面的书的编号应该比当前书多1。
• 每次移动最多会断开三个相连的位置，再重新加入三个相连的位置，因此最多会将3个错误的连接修正，所以如果当前有 $tot$ 个连接，那么最少需要 $\lceil tot / 3 \rceil$ 次操作。
• 因此当前状态 $s$ 的估价函数可以设计成 $f(s) = \lceil tot / 3 \rceil$。

如果当前层数加上 $f(s)$ 大于迭代加深的层数上限，则直接从当前分支回溯。

时间复杂度

理论上最多搜索 $560^4$ 个状态，使用IDA*后实际搜索的状态数量很少。

参考文献

本题解参考《算法竞赛进阶指南》 0x28 IDA* 一节。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 15;

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

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

bool check()
{
    for (int i = 0; i < n; i ++ )
        if (q[i] != i + 1)
            return false;
    return true;
}

bool dfs(int depth, int max_depth)
{
    if (depth + f() > max_depth) return false;
    if (check()) return true;

    for (int l = 0; l < n; l ++ )
        for (int r = l; r < n; r ++ )
            for (int k = r + 1; k < n; k ++ )
            {
                memcpy(w[depth], q, sizeof q);
                int x, y;
                for (x = r + 1, y = l; x <= k; x ++, y ++ ) q[y] = w[depth][x];
                for (x = l; x <= r; x ++, y ++ ) q[y] = w[depth][x];
                if (dfs(depth + 1, max_depth)) return true;
                memcpy(q, w[depth], sizeof q);
            }
    return false;
}

int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        scanf("%d", &n);
        for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);

        int depth = 0;
        while (depth < 5 && !dfs(0, depth)) depth ++ ;
        if (depth >= 5) puts("5 or more");
        else printf("%d\n", depth);
    }

    return 0;
}