<—点个赞吧QwQ

宣传一下算法提高课整理

给定 $n$ 本书，编号为 $1 \sim n$。

在初始状态下，书是任意排列的。

在每一次操作中，可以抽取其中连续的一段，再把这段插入到其他某个位置。

我们的目标状态是把书按照 $1 \sim n$ 的顺序依次排列。

求最少需要多少次操作。

输入格式

第一行包含整数 $T$，表示共有 $T$ 组测试数据。

每组数据包含两行，第一行为整数 $n$，表示书的数量。

第二行为 $n$ 个整数，表示 $1 \sim n$ 的一种任意排列。

同行数之间用空格隔开。

输出格式

每组数据输出一个最少操作次数。

如果最少操作次数大于或等于 $5$ 次，则输出 5 or more。

每个结果占一行。

数据范围

$1 \le n \le 15$

输入样例：

3
6
1 3 4 6 2 5
5
5 4 3 2 1
10
6 8 5 3 4 7 2 9 1 10

输出样例：

2
3
5 or more

思路

我们可以先计算一下每一步的决策数量。

当抽取长度为$i$时，有$n-i+1$种取法，有$n-i$种放法，由于从前放到后面和从后放到前面被算了$2$次，所以每一步的决策数量为$\dfrac{\sum\limits_{i=1}^{n}(n-i)\times(n-i+1)}{2}=\dfrac{15\times 14+14\times 13\times\cdots\times2\times1}{2}=560$
如果暴力枚举，计算量为$560^4$，会$\text{TLE}$

所以我们考虑$\text{IDA}^*$。

估价函数设计：
假设有$cnt$个位置使得相邻的位置并不是相差$1$（即这两个数不能捆在一起处理），而每次移动会改变$3$个数后面的数，所以操作数量为$\lceil\dfrac{cnt}{3}\rceil=\lfloor \dfrac{cnt+2}{3}\rfloor$ 。
然后记得$\text{IDA}^*$是用$\text{IDDFS}$实现的（迭代加深）。

代码

#include <iostream>
#include <cstring>
using namespace std;
const int N = 20;
int n;
int a[N];
int w[5][N];
int f () {
    int ans = 0;
    for (int i = 2;i <= n;i++) ans += a[i - 1] + 1 != a[i];
    return (ans + 2) / 3;
}
bool dfs (int depth,int max_depth) {
    if (depth + f () > max_depth) return false;
    if (f () == 0) return true;
    for (int len = 1;len <= n;len++) {
        for (int l = 1;l + len - 1 <= n;l++) {
            int r = l + len - 1;
            for (int k = r + 1;k <= n;k++) {
                memcpy (w[depth],a,sizeof (a));
                int x,y;
                for (x = r + 1,y = l;x <= k;x++,y++) a[y] = w[depth][x];
                for (x = l;x <= r;x++,y++) a[y] = w[depth][x];
                if (dfs (depth + 1,max_depth)) return true;
                memcpy (a,w[depth],sizeof (w[depth]));
            }
        }
    }
    return false;
}
int main () {
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1;i <= n;i++) cin >> a[i];
        int max_depth = 0;
        while (max_depth < 5 && !dfs (0,max_depth)) max_depth++;
        if (max_depth == 5) puts ("5 or more");
        else cout << max_depth << endl;
    }
    return 0;
}