自动搬运

查看原文

来自洛谷，原作者为

	BK小鹿 如果难过，请你忘了我||afo on 2025.1.1?

搬运于2025-08-24 22:58:29，当前版本为作者最后更新于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;
}