题目描述

给定n本书，编号为1-n。

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

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

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

求最少需要多少次操作。

输入格式
第一行包含整数T，表示共有T组测试数据。

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

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

同行数之间用空格隔开。

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

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

每个结果占一行。

数据范围
1≤n≤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

算法1. IDA* 时间复杂度O(?)

迭代加深 + 估值函数。
估值函数：从终态逆推可以看出,一次移动最多合并三个有序块，所以估价函数为$\lceil$(有序块的数量)/3$\rceil$

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

using namespace std;

const int N = 25;

int n,q[N];

int depth;

int f(){

    int res = 0;

    for(int i=0;i < n - 1;i++)
        if(q[i] + 1!= q[i + 1])
            res ++;

    return (res + 2) / 3;

}
bool dfs(int u)
{
    if(u + f() > depth) return false;
    if(f() == 0) return true;  

    int w[N];

    memcpy(w,q,sizeof w);

    for(int l=0;l<n;l++)
        for(int r=l;r<n;r++)
            for(int k=r+1;k<n;k++)
            {
                int x,y;
                for(x=r+1,y=l;x<=k;x++,y++) q[y] = w[x];
                for(x=l;x<=r;x++,y++) q[y] = w[x];

                if(dfs(u + 1)) return true;

                memcpy(q,w,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]);

        depth = 0;

        while(depth < 5&&!dfs(0)) depth ++;

        if(depth >= 5) puts("5 or more");
        else printf("%d\n",depth);

    }

    return 0;
}`

算法2. 双向BFS 时间复杂度O(2 * 640 ^ 2)

y总埋的坑=。=等个大佬来填坑~。~

不是我懒，主要是我菜，实在Debug不出来~。~