排书

180. 排书 - AcWing题库 给定 $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-j 部分放到k位置上, 只需要把绿色部分和蓝色部分换一下位置即可。

考虑爆搜。 搜索顺序： u为当前变换次数, depth为最大搜索深度

进行到某一步时, 枚举所有摘出来的区间, 然后再枚举放的位置。 返回条件就是遍历一遍当前序列, 若为正序则递归返回。

剪枝优化：

1. 采用迭代加深的方式搜索, 因为题目要求不需要搜的超过4步
2. 插入时只插入到k后面, 组合式搜索避免重复
3. 因为最终状态是全为正序, 对于每次操作的贡献可以通过统计操作后的相邻逆序对数量, 如果减少说明是有效操作, 若增加或者不变则为无效操作。故可以使用IDA-star的优化方式, 定义损失函数计算达成结果的最小步数, 若当前步数加上最小步数大于最大深度, 则直接回溯。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <cmath>
using namespace std;
const int N = 15;
int q[N], w[5][N];
int n;
 
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)
{
    if(u + f() > depth) return false;
    if(f() == 0) return true;
    
    for(int len = 1; len < n ; len++)
    {
        for(int i = 0; i + len - 1 < n; i++)
        {
            int j = i + len - 1;
            for(int k = j+1; k < n; k++)
            {
                // 将i-j放到k位置后面
                memcpy(w[u], q, sizeof q);
                int y = i;
                for(int x = j+1; x <= k; x++, y++) q[y] = w[u][x];
                for(int x = i; x <= j; x++, y++) q[y] = w[u][x];
                if(dfs(u+1,depth))
                {
                    /*cout << u << ": ";
                    for(int i = 0; i < n; i++) cout << w[u][i] << " ";
                    cout << endl;*/
                    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\n";
        else cout << depth << endl;
    }
    return 0;
}