题目描述
给定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
C++ 代码
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=25;
int n;
int q[N];
int 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 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;
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[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];
if(dfs(depth+1,max_depth))return true;
memcpy(q,w[depth],sizeof q);
}
}
return false;
}
int main(){
int T;
scanf("%d",&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++;//迭代加深
//dfs(当前层数,最大可以允许的层数(即最大可允许的步数))
if(depth>=5)puts("5 or more");
else printf("%d\n",depth);
}
return 0;
}