题解：P10488 Booksort

BK小鹿 · 2024-08-10 22:11:26 · 题解

题意简述

给定一个序列，通过几次插入操作，使其变得有序，求最小的操作数。

思路分析

看到这么小的范围，明显爆搜。但是朴素的算法复杂度为四次方，显然会超时。此时考虑双向搜索或 IDA。由于本人太菜了，不会双向搜索，所以决定使用 IDA。

什么是 IDA* 呢？其实就是迭代加深的升级版，我们在搜索的时候提前预估这个节点会产生多少层，如果加上当前层数大于搜索最大层数就提前返回。正确性显而易见，我们只需要写一个估价函数，使他小与等于实际层数就行了。

如何写估价函数呢？显然，假设当前一共有 tot 个错误后继，我们一次移动最理想的情况下能修正三个，直接除以三即可。

剩下的就是套路模版了，非常好写。

AC Code

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 15;

int n;
int q[N], w[5][N];

int f()
{
    int tot = 0;
    for (int i = 0; i + 1 < n; i ++ )
      if (q[i] + 1 != q[i + 1])
        tot ++ ;

    return (tot + 2) / 3;
}

bool dfs(int u, int max_depth)
{
    if (u + f() > max_depth)  return 0;
    if (f() == 0)  return 1;

    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 ++ )
          {
              memcpy(w[u], q, sizeof q);

              int y = l;
              for (int x = r + 1; x <= k; x ++ , y ++ )  q[y] = w[u][x];
              for (int x = l; x <= r; x ++ , y ++ )  q[y] = w[u][x];

              if (dfs(u + 1, max_depth))  return 1;

              memcpy(q, w[u], sizeof q);
          }
      }

    return 0;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> n;
        for (int i = 0; i < n; i ++ )  cin >> q[i];

        int depth = 0;

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

        if (depth >= 5)  puts("5 or more");
        else cout << depth << '\n';
    }

    return 0;
}