AcWing 180. 排书
原题链接
中等
作者:
十六
,
2021-01-21 21:42:05
,
所有人可见
,
阅读 330
#include<bits/stdc++.h>
using namespace std;
const int MAX = 15;
int t, n;
int q[MAX];
int backup[5][MAX];
//估值函数
int f(){
int num = 0;
for(int i=0; i<n-1; i++){
if(q[i]+1!=q[i+1]) num++;
}
return (num+2)/3;
}
bool dfs(int u, int k){
//每次操作,会影响三个关键点
//即每次操作最好情况下能够使三个位置后面紧跟的数字变成有序
//当无序位置为 a 个时,最少需要 a/3(上取整) 次操作,才能使序列变成有序
//如果当前已经操作的次数加上预估的最少操作次数依旧大于当前搜索的操作次数
//则当前的方案一定不可行,需要回溯换其他方案
if(u+f()>k) return false;
//已经达到有序状态,返回成功
if(f()==0) 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 i=r+1; i<n; i++){
memcpy(backup[u], q, sizeof q); //备份当前的序列状态,方便后面恢复现场
//将区间序列插入到某个位置后面,相当于交换相邻两段的位置
int y = l;
for(int x=r+1; x<=i; x++, y++) q[y] = backup[u][x];
for(int x=l; x<=r; x++, y++) q[y] = backup[u][x];
if(dfs(u+1, k)) return true;
memcpy(q, backup[u], sizeof q); //恢复现场
}
}
}
return false;
}
int main(){
scanf("%d", &t);
while(t--){
scanf("%d", &n);
for(int i=0; i<n; i++) scanf("%d", &q[i]);
int k = 0;
while(k<5 && !dfs(0, k)) k++;
if(k>=5) puts("5 or more");
else printf("%d\n", k);
}
return 0;
}