python/TangDou/AcWing/IDAstar/180_IDAStar.cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 16; // 1≤n≤15
int a[N];         // 记录书的排列情况
int n;            // 书的数量
int depth;        // 最少的操作步数

// 估值函数:实时计算此状态到终止状态最少的步数
// 这个IDA*的估价函数，本质上与A*的是一样的意思，都是在每个状态下可以获取到距离理想状态（即每个数字后序都大1）的错误后继个数
int f() {
    int cnt = 0;
    // 计算前后非+1递增的 错误后继的对数
    for (int i = 0; i < n - 1; i++)
        if (a[i] + 1 != a[i + 1]) cnt++;
    return (cnt + 2) / 3; // 每次移动，最多能解决三个错误后继，如果现在有cnt个错误后继，最少需要 ⌈cnt/3⌉次操作
}

// u:已经操作的步数
bool dfs(int u) {
    int t = f();                     // 未来最小的操作步数
    if (t == 0) return true;         // 已完成排序
    if (u + t > depth) return false; // 当前操作步数+未来预期最小>　迭代加深的深度 表示没有找到结果，返回。及时剪枝

    for (int len = 1; len < n; len++) { // 枚举抽取长度 len∈[1,n-1)
        // st: 起始下标
        // st ∈ [0,n-1] 左边界很好理解，现在看一下右边界：st+len，也就是终止坐标，不能大于n-1
        for (int st = 0; st + len < n; st++) {
            // ed:结束下标
            // 注意：只考虑右移，不考虑左移，因为这是一个对称的操作，A串向B串后面右移，相当于B串向A串前面左移
            for (int ed = st + len; ed < n; ed++) {
                // 序列右移
                // reverse()：这是一个前闭后开的区间[)，时刻要提醒自己注意！
                reverse(a + st, a + st + len);
                reverse(a + st + len, a + ed + 1);
                reverse(a + st, a + ed + 1);

                // 本轮实现了一次右移，那么，这条路线是否可以成功抵达终点，就依赖于我的后续子孙了
                if (dfs(u + 1)) return true;

                // 后面串的长度,还原现场,回溯
                reverse(a + st, a + ed - len + 1);
                reverse(a + ed + 1 - len, a + ed + 1);
                reverse(a + st, a + ed + 1);
            }
        }
    }
    return false;
}

// AC 	204 ms
int main() {
    int T; // T组测试数据
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n); // 表示书的数量
        for (int i = 0; i < n; i++) scanf("%d", &a[i]);
        /*
         最少操作次数
         解释：因为可能书本来天生就是有序，即每本书n后面都是n+1，完全合格的顺序，这时不用调整，最少操作数为0
         需要从0开始查询最少操作次数
        */
        depth = 0;
        while (depth < 5 && !dfs(0)) depth++; // 有层数限制的dfs，迭代加深

        if (depth >= 5) // 最少操作次数大于或等于5次
            puts("5 or more");
        else
            printf("%d\n", depth); // 最少操作次数
    }
    return 0;
}