IDA* AcWing 180. 排书

原题链接

AcWing 180. 排书

算法标签

搜索 IDA*

思路

先考虑每一步的决策数量：
当抽取长度为 i 的一段时，有 $n-i+1$ 种抽法，对于每种抽法，有 $n-i$ 种放法。另外，将某一段向前移动，等价于将跳过的那段向后移动，因此每种移动方式被算了两遍，所以每个状态总共的分支数量是：${\sum }_{i=1}^N(n-i)\ast (n-i+1)/2=(15\ast 14+14\ast 13+\dots +2\ast 1)/2=560$。

考虑在四步以内解决，最多有 $560^4$ 个状态，会超时。
可以使用双向BFS或者IDA*来优化。

我们用IDA*来解决此题。
估价函数：

估价函数需要满足：不大于实际步数
在最终状态下，每本书后面的书的编号应该比当前书多1。
每次移动最多会断开三个相连的位置，再重新加入三个相连的位置，因此最多会将3个错误的连接修正，所以如果当前有 tot 个连接，那么最少需要 ⌈tot/3⌉ 次操作。
因此当前状态 s 的估价函数可以设计成 f(s)=⌈tot/3⌉。
如果当前层数加上 f(s) 大于迭代加深的层数上限，则直接从当前分支回溯。

时间复杂度
理论上最多搜索 $560^4$ 个状态，使用IDA*后实际搜索的状态数量很少。
移动操作

代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define ump unordered_map
#define pq priority_queue
#define rep(i, a, b) for(int i=a;i<b;++i)
#define Rep(i, a, b) for(int i=a;i>b;--i)
using namespace std;
typedef pair<int, int> PII;
const int N = 15;
//int t, n, m, cnt, ans; 
int q[N];
// 恢复现场 进行数据备份
int w[5][N];
int n;
inline int rd(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
void put(int x) {
    if(x<0) putchar('-'),x=-x;
    if(x>=10) put(x/10);
    putchar(x%10^48);
}
// 估价函数
int f(){
    int cnt=0;
    rep(i, 0, n-1){
        if(q[i+1]!=q[i]+1){
            cnt++;
        }
    }
    return (cnt+2)/3;
}
// 检查序列是否已经有序
bool check(){
    rep(i, 0, n-1){
        if(q[i+1]!=q[i]+1){
            return false;
        }
    }
    return true;
}
// d: 当前迭代深度; md: 迭代加深最大深度
bool dfs(int d, int md){
	// 如果当前层数加上f(s)大于迭代加深的层数上限，则直接从当前分支回溯。
    if(d+f()>md){
        return false;
    }
    if(check()){
        return true;
    }
    // 先遍历长度
    rep(len, 1, n+1){
    	// 再遍历左端点
        rep(l, 0, n-len+1){
            int r=l+len-1;
            // 将当前区间放置后续区间
            rep(k, r+1, n){
            // 存储当前状态， 便于搜索后进行现场恢复
                memcpy(w[d], q, sizeof q);
                int x, y;
                // 将上图中绿色部分移动到红色部分
                for(x=r+1, y=l; x<=k; ++x, ++y){
                    q[y]=w[d][x];
                }
                // 将上图中红色部分移动到绿色部分
                for(x=l; x<=r; ++x, ++y){
                    q[y]=w[d][x];
                }
                // 若下一层搜索成功 
                if(dfs(d+1, md)){
                    return true;
                }
                // 恢复现场
                memcpy(q, w[d], sizeof q);
            }
        }
    }
    return false;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t=rd();
	while(t--){
	    n=rd();
	    rep(i, 0, n){
	        q[i]=rd();
	    }
	    int d=0;
	    while(d<5&&!dfs(0, d)){
	        d++;
	    }
	    if(d>=5){
	        puts("5 or more");
	    }else{
	        printf("%lld\n", d);
	    }
	}
	return 0;
}

参考文献
AcWing 180. 排书y总题解
AcWing 180. 排书y总视频讲解

原创不易
转载请标明出处
如果对你有所帮助 别忘啦点赞支持哈