|
|
#include <iostream>
|
|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
const int N = 20;
|
|
|
int q[N];
|
|
|
int g[10][N];
|
|
|
int n;
|
|
|
|
|
|
int f() {
|
|
|
int tot = 0;
|
|
|
for (int i = 1; i <= n - 1; i++)
|
|
|
if (q[i] + 1 != q[i + 1])
|
|
|
tot++;
|
|
|
|
|
|
return (tot + 2) / 3;
|
|
|
}
|
|
|
bool panduan() {
|
|
|
for (int i = 1; i <= n; i++)
|
|
|
if (q[i] != i)
|
|
|
return false;
|
|
|
return true;
|
|
|
}
|
|
|
bool dfs(int u, int depth) {
|
|
|
if (u + f() > depth) return false;
|
|
|
|
|
|
if (panduan()) {
|
|
|
return true;
|
|
|
}
|
|
|
for (int len = 1; len < n; len++)
|
|
|
for (int qi1 = 1; qi1 + len - 1 <= n; qi1++) {
|
|
|
int r = qi1 + len;
|
|
|
for (int wai = r; wai <= n; wai++) {
|
|
|
memcpy(g[u], q, sizeof q);
|
|
|
// memccpy(g[u],q,sizeof q);
|
|
|
int i, j;
|
|
|
for (i = qi1, j = r; j <= wai; i++, j++)
|
|
|
q[i] = g[u][j];
|
|
|
for (j = qi1; j <= qi1 + len - 1; i++, j++)
|
|
|
q[i] = g[u][j];
|
|
|
if (dfs(u + 1, depth)) {
|
|
|
return true;
|
|
|
}
|
|
|
memcpy(q, g[u], sizeof g[u]);
|
|
|
}
|
|
|
}
|
|
|
|
|
|
return false;
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
freopen("180.in", "r", stdin);
|
|
|
|
|
|
// 记录开始时间
|
|
|
clock_t begin = clock();
|
|
|
|
|
|
int T;
|
|
|
scanf("%d", &T);
|
|
|
while (T--) {
|
|
|
scanf("%d", &n); // 表示书的数量
|
|
|
for (int i = 1; i <= n; i++) scanf("%d", &q[i]);
|
|
|
|
|
|
int depth = 0;
|
|
|
while (depth < 5 && !dfs(0, depth)) depth++;
|
|
|
// while (depth <= 5 && !dfs(0, depth)) depth++;
|
|
|
// 会有1个测试点超时
|
|
|
// 提醒我们：在使用迭代加深时，要严格注意depth的边界范围
|
|
|
if (depth < 5)
|
|
|
cout << depth << endl;
|
|
|
else
|
|
|
cout << "5 or more" << endl;
|
|
|
}
|
|
|
|
|
|
// 记录结束时间
|
|
|
clock_t end = clock();
|
|
|
cout << "Running time:" << (double)(end - begin) / CLOCKS_PER_SEC * 1000 << "ms" << endl;
|
|
|
|
|
|
return 0;
|
|
|
} |
