思路与算法

在排列末尾补哨兵n+1，把相邻差的绝对值不为1的边数h作为估价。前缀翻转不改变内部相邻差，只改变切口一条边，因此一次最多消除一个断点。IDA星按g+h阈值搜索，将最小超界值作为下一轮阈值；优先尝试估价较小的翻转，并禁止连续使用同一长度。

正确性说明

h是到目标所需操作数的下界。h=0时，含末尾哨兵的排列只能是完整升序链，目标识别正确。阈值内枚举所有可能有效序列；连续相同翻转可相消，删掉它不会丢失最优解。首次找到目标的阈值即最少操作数。

复杂度

设最优深度D，最坏搜索节点数为指数级O((n-1)^D)，每节点枚举、排序和翻转最坏O(n²+nlogn)，总时间可按其乘积上界估计；递归各层候选数组O(Dn)，输入初始化O(n)。不宣称多项式时间。

易错点

长度1没有作用。用绝对差而非有向差计算断点，反转内部相邻关系不影响估价。哨兵不参加翻转；只用h=0判目标依赖输入确为1至n排列。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int n, a[25];
int dfs(int g, int h, int bound, int last) {
    if (g + h > bound)
        return g + h;
    if (!h)
        return -1;
    int next = 100;
    vector<pair<int, int>> moves;
    for (int k = 2; k <= n; k++)
        if (k != last) {
            int z = h - (abs(a[k - 1] - a[k]) != 1) + (abs(a[0] - a[k]) != 1);
            moves.push_back({z, k});
        }
    sort(moves.begin(), moves.end());
    for (auto p : moves) {
        if (g + 1 + p.first > bound) {
            next = min(next, g + 1 + p.first);
            continue;
        }
        reverse(a, a + p.second);
        int v = dfs(g + 1, p.first, bound, p.second);
        reverse(a, a + p.second);
        if (v < 0)
            return -1;
        next = min(next, v);
    }
    return next;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 0; i < n; i++)
            cin >> a[i];
        a[n] = n + 1;
        int h = 0;
        for (int i = 0; i < n; i++)
            h += abs(a[i] - a[i + 1]) != 1;
        int b = h;
        while (true) {
            int t = dfs(0, h, b, 0);
            if (t < 0)
                break;
            b = t;
        }
        cout << b << '\n';
    }
}