题目描述

给定$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

前置芝士：

IDA*算法：
估价函数 + 迭代加深
这里的估价函数与A*算法的估价函数要求是一致的，也就是估计值不大于未来的实际步数
IDA*算法相对于原先的迭代加深算法的不同是：如果当前深度 + 未来估计步数 > 深度限制，则就需要进行回溯。

解题思路：
这道题我们发现，对于每一个状态而言，如果我们交换的长度为$i$的子序列，则有$n-i+1$种选择，对于每种长度可以插入的位置有$n-i$个，故总共的状态数有$(n-i+1) \* (n-i)$种，估算下来大致有$560$种，而题目中要求最多扩展4层，故最终的状态数为$560 ^ 4$种，这样是会超时的，这里可以有两种解法来解决：

算法1

(双向BFS)

(最后一个点TLE了，大佬们帮忙看看有什么地方可以优化，不胜感激！！！！)
由于直到最终状态和起始状态，所以可以从两端同时进行广搜，产生交点就返回此时的步数。

时间复杂度

由于这里最多会扩展$560 ^ 2$个点，所以理论上最终的复杂度为$O(560 ^ 2)$。 (但是实际情况好像慢好多。。。。。

import java.io.*;
import java.util.*;

class Main {
    static int N = 20;
    static char[] cy = new char[N];
    static int n;
    static String st, ed;
    static int res;

    static int extend(Queue<String> q, Map<String, Integer> d1, Map<String, Integer> d2) {

        int sz = q.size();

        while (sz-- > 0) {
            String t = q.poll();

            char[] a = t.toCharArray();
            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++) {
                        cy = Arrays.copyOf(a, N);
                        int y = l;
                        for (int x = r + 1; x <= k; x++) a[y++] = cy[x];
                        for (int x = l; x <= r; x++) a[y++] = cy[x];
                        String cur = "";
                        for (int i = 0; i < n; i++) cur += a[i];
                        a = Arrays.copyOf(cy, N);
                        if (d2.containsKey(cur)) return d1.get(t) + d2.get(cur) + 1;
                        if (d1.containsKey(cur)) continue;
                        q.add(cur);
                        d1.put(cur, d1.get(t) + 1);
                    }
                }
            }
        }

        return 5;
    }

    static int bfs() {

        Map<String, Integer> d1 = new HashMap<String, Integer>();
        Queue<String> q1 = new LinkedList<String>();
        Map<String, Integer> d2 = new HashMap<String, Integer>();
        Queue<String> q2 = new LinkedList<String>();

        q1.add(st); d1.put(st, 0);
        q2.add(ed); d2.put(ed, 0);

        if (st.equals(ed)) return 0;

        int cnt = 4; // 限制扩展4次,保证q1和q2各扩展两层
        while (cnt-- > 0) {

            int t = -1;
            if (q1.size() <= q2.size()) t = extend(q1, d1, d2);
            else t = extend(q2, d2, d1);

            if (t < 5) return t;
        }

        return 5;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(in.readLine());

        while (T-- > 0) {
            n = Integer.parseInt(in.readLine());
            String[] cur = in.readLine().split(" ");
            st = "";
            ed = "";
            for (int i = 0; i < n; i++) {
                int tmp = Integer.parseInt(cur[i]);
                st += (char) (tmp + 'A' - 1);
                ed += (char) (i + 'A');
            }

            int t = bfs();

            if (t >= 5) System.out.println("5 or more");
            else System.out.println(t);
        }
    }
}

算法2

(IDA*算法)

IDA*算法，这里我们可以发现，移动一串连续的序列最多可以改变3个数字的后继，所以我们每一次统计当前序列中一共有多少个不合法的后继，除以3上取整就是当前状态的估价函数的值，之后采用迭代加深的方法，从0-4依次限制搜索的深度，然后从起始状态做DFS。

时间复杂度

不好估计。。

参考文献

算法提高课

import java.io.*;
import java.util.*;

class Main{
    static int N = 20;
    static int[] a = new int[N];
    static int[][] cy = new int[5][N]; // 用作拷贝数组
    static int n;

    static int f(){
        int tol = 0;
        for(int i=0; i<n-1; i++){
            if(a[i+1] != a[i] + 1) tol ++; 
        }
        return (tol + 2) / 3;
    }

    static boolean 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 i=0; i+len-1<n; i++){
                int j = i + len - 1;
                for(int k=j+1; k<n; k++){
                    cy[depth] = Arrays.copyOf(a, N);
                    int y = i;
                    for(int x = j+1; x<=k; x++) a[y ++] = cy[depth][x];
                    for(int x = i; x<=j; x++) a[y++] = cy[depth][x];

                    if(dfs(depth+1, max_depth)) return true;

                    a = Arrays.copyOf(cy[depth], N);
                }
            }
        }

        return false;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

        int T = Integer.parseInt(in.readLine());

        while(T -- > 0){
            n = Integer.parseInt(in.readLine());
            String[] cur = in.readLine().split(" ");
            for(int i=0; i<n; i++) a[i] = Integer.parseInt(cur[i]);

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

            if(depth == 5) System.out.println("5 or more");
            else System.out.println(depth);
        }
    }
}