AcWing 180.排书

算法思路

IDA*

该算法为A*和迭代加深的结合，其中相对于A*的估价函数额外增加了基于估价函数超过迭代层数的剪枝。

排书交换

本题中由于可以一次性将连续的一串书本直接插入到后面的某个位置，故可以考虑从遍历长度入手。

交换的过程可以如下所示

-----|-----|------|--------
     l     r      k   

整个交换过程可以分为下面几步

• 首先将原始的数组b复制一份到备用数组w[depth]
• 将w[depth]的r + 1到k的部分复制到p的l到l + k - r区域
• 将w[depth]的l到r部分复制到p的对应剩余部分。
• ...

在这里我们需要将l到r的书籍插入到r + 1的位置，可以考虑使用如下方式

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

算法实现

#include <iostream>
#include <cstring>

using namespace std;

const int N = 16;

int b[N], n, c;
int w[5][N];

int f()
{
    int cnt = 0;
    for (int i = 0; i < n - 1; ++i)
    {
        if (b[i] != b[i + 1] - 1) cnt ++;
    }
    
    return (cnt + 2) / 3;
}

bool check()
{
    for (int i = 0; i < n - 1; ++i)
    {
        if (b[i] != b[i + 1] - 1) return false;
    }
    return true;
}

bool dfs(int u, int max_step)
{
    if (u + f() > max_step) return false;
    if (check()) return true;
    
    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], b, sizeof w[u]);
                int x, y;
                for (x = r + 1, y = l; x <= k; x ++, y ++) b[y] = w[u][x];
                for (x = l; x <= r; x ++, y ++) b[y] = w[u][x];
                if (dfs(u + 1, max_step)) return true;
                memcpy(b, w[u], sizeof w[u]);
            }
        }
    }
    
    return false;
}

int main()
{
    cin >> c;
    while(c --)
    {
        cin >> n;
        for (int i = 0; i < n; ++i) cin >> b[i];
        
        int max_step = 0;
        while(max_step < 5 && !dfs(0, max_step)) max_step ++;
        
        if (max_step >= 5) cout << "5 or more\n";
        else cout << max_step << endl;
    }
}