@zzzc18
2018-01-18T20:33:43.000000Z
字数 1413
阅读 1190
TEST
搜索
【题目描述】
给定一个1~n的排列x,每次你可以将x1~xi翻转。你需要求出将序列变为
升序的最小操作次数。有多组数据。
【输入数据】
第一行一个整数t表示数据组数。
每组数据第一行一个整数n,第二行n个整数x1~xn。
【输出数据】
每组数据输出一行一个整数表示答案。
【样例输入】
1
8
6 1 3 2 4 5 7
【样例输出】
7
【数据范围】
对于100%的测试数据,t=5,n<=25。
对于测试点1,2,n=5。
对于测试点3,4,n=6。
对于测试点5,6,n=7。
对于测试点7,8,9,n=8。
对于测试点10,n=9。
对于测试点11,n=10。
对于测试点i(12<=i<=21),n=i。
对于测试点22,23,n=22。
对于测试点24,25,n=23。
考试的时候已经猜到是 IDA*
了,可是一直没想出来估价函数是啥,写了个迭代加深搜索骗了个暴力分。。。
考虑到这是一个排列,最终的状态一定是 num[i]+1==num[i+1]
。
而每次交换最多只会改变一组相邻元素的差值
所以对于某一个状态,相邻的元素之差大于 的个数就可以作为估价函数的值,因为最优解步数不小于这个。
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 36;
int n;
int tmp[MAXN];
int num[MAXN];
int ans;
bool check(){
for(int i=1;i<n;i++)
if(num[i]+1!=num[i+1])
return false;
return true;
}
void SWAP(int l,int r){
for(int i=l;i<=r;i++)
tmp[i]=num[i];
for(int i=r,j=l;i>=l;i--,j++)
num[i]=tmp[j];
}
bool H(int x,int limit){
int re=0;
for(int i=1;i<n;i++){
if(abs(num[i]-num[i+1])>1)
re++;
}
return re+x<=limit;
}
void DFS(int x,int limit){
if(x==limit+1){
if(check())
ans=limit;
return;
}
for(int i=1;i<=n;i++){
if(ans!=2*n+1)
return;
SWAP(1,i);
if(H(x,limit))
DFS(x+1,limit);
SWAP(1,i);
}
}
void solve(){
ans=2*n+1;
if(check()){
puts("0");
return;
}
for(int i=1;i<=2*n;i++){
DFS(1,i);
if(ans!=2*n+1)
break;
}
printf("%d\n",ans);
}
int main(){
freopen("sequence.in","r",stdin);
freopen("sequence.out","w",stdout);
int kase;
scanf("%d",&kase);
while(kase--){
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
solve();
}
return 0;
}