[AHOI2012] 铁盘整理

题目链接

洛谷

题目分析

首先 $ N $ 的值较小，考虑进行搜索。

该题求的是最小翻转次数，次数是不确定的，并且可能会搜索很多次无功而返，搜索树会很深，如果一直搜下去容易超时，所以考虑迭代加深搜索。

而该题如果暴力搜索会超时，对于 IDDFS，我们可以使用估价函数进行剪枝，将其升级为 IDA*。

我们需要用估计函数来估计期望最小翻转次数，如果在期望的最少次数内需要的次数超过此次迭代的搜索深度上限，就肯定无法完成了，不用继续搜索下去了。

那么该如何设计估价函数呢？

记 $ a_{i} $ 为第 $ i $ 个铁盘应当处于的位置，如果 $ |a_{i} - a_{i-1}| = 1 $，那么 $ a_{i} $ 和 $ a_{i-1} $ 就有可能是连续的（即 $ a_{i-1} + 1 = a_{i} $ ），应当作为整体翻转。而当 $ a_{i-1} = a_{i} + 1 $ 时，两个数字是倒着的，至少要一次翻转。不过，估价函数是用来剪枝的，可以不剪得那么精确，这种情况下可以不对期望最小翻转次数进行更改。当 $ |a_{i} - a_{i-1}| > 1 $ 时，这两个数一定要让它们分开，期望翻转次数需要加一。

代码实现

#include <bits/stdc++.h>

using namespace std;

int n;
int num[105];
int id[105];

bool cmp(int a, int b)
{
    return num[a] < num[b];
}

void reverse(int l, int r)
{
    for (int i = l, j = r; i <= j; i++, j--) {
        swap(num[i], num[j]);
    }
}

int evaluate()
{
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (abs(num[i] - num[i - 1]) != 1) cnt++;
    }
    /*
    注意当第一个元素不为 1 时也会让最小期望翻转次数加一
    但第一个元素不应和不存在的第 0 个元素一起翻转
    所以应当减去 1
    */
    return cnt - 1; 
}

bool dfs(int depth, int maxd)
{
    if (depth > maxd) return 0;
    int v = evaluate();
    if (depth + v > maxd) {
        return 0;
    }

    bool flag = 1;
    for (int i = n; i >= 1; i--) {//从最底层开始，优化搜索顺序
        if (num[i] == i && flag) {
            if (i == 1) return 1;
            continue;//已经有序的不用继续排了
        }
        flag = 0;
        reverse(1, i);
        if (dfs(depth + 1, maxd)) {
            return 1;
        }
        reverse(1, i);
    }

    return 0;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> num[i];
        id[i] = i;
    }

    //离散化操作，将铁盘半径转化为应当处于的位置
    sort(id + 1, id + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        num[id[i]] = i;
    }

    for (int maxd = evaluate();; maxd++) {//从预估翻转次数开始搜索
        if (dfs(0, maxd)) {
            cout << maxd << endl;
            break;
        }
    }

    return 0;
}