题目描述
给定n本书,编号为1-n。
在初始状态下,书是任意排列的。
在每一次操作中,可以抽取其中连续的一段,再把这段插入到其他某个位置。
我们的目标状态是把书按照1-n的顺序依次排列。
求最少需要多少次操作。
样例
输入样例:
3
6
1 3 4 6 2 5
5
5 4 3 2 1
10
6 8 5 3 4 7 2 9 1 10
输出样例:
2
3
5 or more
算法1
(IDA*)
考虑抽取长度为$i$的时候,总共有$n - i + 1$种抽取方法, 总共有$n - i$ (因为排除了原地放置,所以已经将次数-1)种插入的位置。
因此每个分支的状态数量= $\Sigma^n_{i = 1} (n - i) * (n - i + 1)/ 2 = 560$.($/2$是因为两个线段1,2, 1往后放和2往前放是同一种)。
如果暴力搜索4层, 那么总共有$560 * 560 * 560 * 560 = 560^4$,太多。
因此采用迭代加深 + A*.
可以发现,每次裁剪掉一个线段后,最多可以使得3个位置上的点变成正确的位置,设总共裁剪tot
次;
那么至少需要操作$\lceil tot / 3 \rceil$次。
因此 估价函数可以采用$f(tot) = \lceil tot / 3 \rceil$
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 15;
int q[N], w[5][N];
int 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 check(){
for (int i = 0; i < n; i ++ )
if (q[i] != i + 1) return false;
return true;
}
bool dfs(int depth, int max_depth){
if (depth + f() > max_depth) return false; //注意这里条件是> max_depth, 而不是> 题目条件中的5,因为是按照迭代加深,1层1层depth搜索的。
if (check()) return true;
for (int l = 0; l < n; l ++ ) //枚举抽取线段的起点
for (int r = l; r < n; r ++ ) //枚举抽取线段的终点。
for (int k = r + 1; k < n; k ++ ){//枚举抽取了的线段,该往哪个落脚点放。这里规定一律往后放,避免重复。
memcpy(w[depth], q, sizeof q);//保存现场
int x, y;
for (x = r + 1, y = l; x <= k; x ++, y ++ ) q[y] = w[depth][x];//先把后面的往前移动
for (x = l; x <= r; x ++, y ++) q[y] = w[depth][x]; //l到r这段搬到后面
if (dfs(depth + 1, max_depth)) return true;
memcpy(q, w[depth], sizeof q);
}
return false;
}
int main(){
int T;
cin >> T;
while (T --){
scanf("%d", &n);
for (int i = 0; i < n; i ++ ) scanf("%d", &q[i]);
int depth = 0;
while (depth < 5 && !dfs(0, depth)) depth ++;
if (depth >= 5) puts("5 or more");
else printf("%d\n", depth);
}
return 0;
}