给定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
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 15 ;
int p[N];
int mc[5][N];
int T;
int n ;
int f()//估計函數
{
int tol = 0;
for(int i = 0; i+1 < n ; i++)
{
if(p[i+1] !=p[i] + 1)tol++;
}
return (tol +2) / 3;
}
bool dfs(int u , int depath)//当前需要的操作次数 总共能够遍历多少层
{
if(u + f() > depath) return false;
if(f() == 0) return true;
for(int len = 1; len <= n ; len ++)
{
for(int l = 0 ; len + l - 1 < n ; l ++)
{
int r = len + l - 1;
for(int k = r + 1; k < n ; k++)
{
memcpy(mc[u], p , sizeof p);//先copy下来 便于后面回溯
int y = l ;
for(int x = r + 1 ; x <= k ; x ++,y ++)p[y] = mc[u][x];//用来置换替换后的位置
for(int x = l ; x <= r; x++ , y ++ )p[y] = mc[u][x];//后半段
if(dfs(u + 1, depath))return true;
memcpy(p, mc[u] , sizeof p);//回溯
}
}
}
return false;
}
int main()
{
cin >> T;
while(T--)
{
cin >> n ;
for(int i = 0 ; i < n ; i ++)
cin >> p[i];
int depath = 0 ;
while(depath < 5 && !dfs(0,depath)) ++depath;
if(depath >= 5) puts("5 or more");
else cout << depath << endl;
}
return 0;
}