记录编号	557376	评测结果	AAAAAAA
题目名称	[POJ 3460]书籍排列	最终得分	100
用户昵称	Oasiz	是否通过	通过
代码语言	C++	运行时间	0.027 s
提交时间	2020-11-13 19:52:49	内存使用	3.90 MiB

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int N = 100;
int q[N];
int stp[5][N];
int n;
int f(){
	int ans=0;
	for(int i = 0; i < n - 1; i++) {
		if(q[i + 1] != q[i] + 1)
			ans++;
	}
	return (ans+2)/3;//最少修改tot/3次 
}
bool check() {
	for(int i = 0; i < n; i++) {
		if(q[i] != i + 1)
			return false;
	}
	return true;
}
bool dfs(int depth, int maxx) {//限制1~4 
	if(depth + f() > maxx) return false;
	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(stp[depth], q, sizeof(q));
				int y, x;
				for(x = r + 1, y = l; x <= k; x++, y++){
					q[y] = stp[depth][x];
				}
				for(x = l; x <= r; x++, y++ ){
					q[y] = stp[depth][x];
				}
				if(dfs(depth + 1, maxx)) return true;
				memcpy(q, stp[depth], sizeof(q));
			}
		}
	}
	return false;
}
int main() {
	freopen("booksort.in","r",stdin);
	freopen("booksort.out","w",stdout);
	int t;
	cin >> t;
	while(t--){
		cin >> n;
		for(int i = 0; i < n; i++){
			cin >> q[i];
		}
		int depth = 0;
		while(depth<5&&!dfs(0,depth))depth++;
		if(depth>=5)cout<<"5 or more"<<endl;
		else cout<<depth<<endl;
	}
	return 0;
}