给定n本书,编号为1-n。
在初始状态下,书是任意排列的。
在每一次操作中,可以抽取其中连续的一段,再把这段插入到其他某个位置。
我们的目标状态是把书按照1-n的顺序依次排列。
求最少需要多少次操作。
输入格式
第一行包含整数T,表示共有T组测试数据。
每组数据包含两行,第一行为整数n,表示书的数量。
第二行为n个整数,表示1-n的一种任意排列。
同行数之间用空格隔开。
输出格式
每组数据输出一个最少操作次数。
如果最少操作次数大于或等于5次,则输出”5 or more”。
每个结果占一行。
数据范围
1≤n≤15
输入样例:
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
用idea*写,然后这题的朴素枚举是会超时的,当然还有可以使用双向bfs优化,我后面会补。然后,搜索顺序的话,就暴力枚举区间几点和长度,然后去枚举插入的点,去更新数组,这里需要回溯一下。然后我们考虑估价函数,我们可以发现每一次的联结,会断开三个点,联结三个点,最好的情况这三个点先开始全是非法的,交换之后变成合法的,那么我们的估价函数就变成了非法的点数除上3向上取整,这里一个小技巧等价于+2除以3向下取整。
#include<cstdio>#include<iostream>#include<algorithm>#include<queue>#include<cstring>#include<cmath>#include<stack>using namespace std;const int maxn=15;int n;int a[maxn];int w[5][maxn];bool check () { for (int i=0;i<n;i++) { if (a[i]!=i+1) return false; } return true;}int f() { int tot=0; for (int i=0;i+1<n;i++) { if (a[i]!=a[i+1]-1) tot++; } return (tot+2)/3;}bool dfs (int deep,int maxdeep) { if (deep+f()>maxdeep) 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[deep],a,sizeof (a)); int x,y; for (x=r+1,y=l;x<=k;y++,x++) a[y]=w[deep][x]; for (x=l;x<=r;x++,y++) { a[y]=w[deep][x]; } if (dfs (deep+1,maxdeep)) return true; memcpy (a,w[deep],sizeof (a)); } } return false;}int main () { int t ; cin>>t; while (t--) { memset (a,0,sizeof (a)); cin>>n; for (int i=0;i<n;i++) cin>>a[i]; int deepth=0; while (deepth<5&&!dfs (0,deepth)) deepth++; if (deepth>=5) cout<<"5 or more"<<endl; else cout<<deepth<<endl; } return 0;}