题解 P2534 【[AHOI2012]铁盘整理】

· · 题解

Description

给定一个长度为 n 互不相同的序列 a_i，每次操作可以将第 1 \sim i\ (1 \leq i \leq n) 个数翻转，求最少几次操作可以使它变成升序数列。(1 \leq n \leq 50, 1 \leq a_i \leq 100)

Solution

考虑 \rm IDA^* 。

先离散化，保证最后得到的数列为 1,2,3, \ldots, n 。

本题中的 最完美估价：

a[n + 1] = n + 1;

inline int h() {
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
        cnt += abs(a[i] - a[i + 1]) != 1;
    return cnt;
}

显然一次翻转最多只能改变一对相邻数的差（比如翻转第 1 \sim 3 个数只能改变第 3 个数与第 4 个数的差）。因此对于一个序列，有多少对相邻的数差不为 1，就至少要翻转多少次。不要忘记把第 n + 1 个数设为 n + 1，因为如果翻转第 1 \sim n 个数，我们也可以认为改变了第 n 个数与第 n + 1 个数的差。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

template <class T>
inline void read(T &x) {
    x = 0;
    char c = getchar();
    bool f = 0;
    for (; !isdigit(c); c = getchar()) f ^= c == '-';
    for (; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
    x = f ? -x : x;
}

template <class T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10) ++len;
    for (; len; --len, x %= y, y /= 10) putchar(x / y + 48);
}

const int MAXN = 50;
int n, a[MAXN + 5], b[MAXN + 5];
bool sol;

inline int h() {//最完美估价 
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
        cnt += abs(a[i] - a[i + 1]) != 1;
    return cnt;
}

void dfs(int g, int f, int pre) {
    if (sol || g + h() > f) return;//预估步数
    if (!h()) {
        sol = 1;//找到答案 
        return;
    }
    for (int i = 1; i <= n; ++i) {
        if (i == pre) continue;//保证不与上一次翻转的长度相同 
        reverse(a + 1, a + i + 1);//翻转 
        dfs(g + 1, f, i);
        reverse(a + 1, a + i + 1);//回溯 
    }
}

int main() {
    read(n);
    for (int i = 1; i <= n; ++i) {
        read(a[i]);
        b[i] = a[i];
    }
    sort(b + 1, b + n + 1);
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;//离散化 
    a[n + 1] = n + 1;
    for (int i = 0; ; ++i) {//迭代加深 
        sol = 0;
        dfs(0, i, 0);
        if (sol) {
            write(i);
            putchar('\n');
            break;
        }
    }
    return 0;
}