大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
给定 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
题解
IDA*，每一次变动都会改变3个数的后继，所以我们可以先统计每个数的后继，然后看看当前状态是否能达到要求。
- IDA*
#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 1e2;
string t;
int f(){
int tot = 0;
for(int i = 1;i < n;i ++)
if(t[i - 1] != t[i] - 1)tot ++;
return (tot + 2) / 3;
}
bool IDAstar(int u,int maxn){
if(f() > maxn - u)return false;
if(u == maxn){
return true;
}
string temp = t;
for(int len = 1;len <= n - 1;len ++){
for(int l = 0;l <= n - len;l ++){
int r = l + len - 1;
string substr = temp.substr(l,r - l + 1);
for(int k = r + 1;k < n;k ++){
t.insert(k + 1,substr);
t.erase(l,r - l + 1);
if(IDAstar(u + 1,maxn))return true;
t = temp;
}
}
}
return false;
}
int a[N];
int main(){
int T;
cin>>T;
while(T --){
cin>>n;
t = "";
for(int i = 0;i < n;i ++){
cin>>a[i];
t += a[i];
}
int maxn = 0;
while(maxn <= 4 && IDAstar(0,maxn) == false ){
maxn ++;
}
if(maxn == 5){
cout<<"5 or more"<<endl;
}
else cout<<maxn<<endl;
}
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/169133.html原文链接：https://javaforall.net
