标签:迭代加深搜索,IDA*
题目
序列(sequence)
【题目描述】
给定一个1~n的排列x,每次你可以将x1~xi翻转。你需要求出将序列变为升序的最小操作次数。有多组数据。
【输入数据】
第一行一个整数t表示数据组数。
每组数据第一行一个整数n,第二行n个整数x1~xn。
【输出数据】
每组数据输出一行一个整数表示答案。
【样例输入】
1
8
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。
分析
我的dfs姿势很成问题,样例都搜不过去QwQ
他们怎么乱搞几下就上了那么多分
感觉这题就是随便卡一下就多了8分那种
正解是迭代加深搜索+剪枝,反正可以过
我们发现每次翻转只会改变一对相邻数对,因此对于一个状态求出相差>1的相邻数对的数量,剩余步数一定大于这个值。
他们好多人用IDA*过了这题,珂学大爷
code
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read()
{
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
const int maxn=26;
int a[maxn],ans,T,n,p;
void rev(int x){
rep(i,1,x>>1)swap(a[i],a[x-i+1]);
}
void dfs(int x,int y){
if(x+y>ans)return;//剪枝,如果总步数超出范围就return
int pos=0;
rep(i,1,n)
if(a[i]!=i){pos=i;break;}
if(pos==0){p=1;return;}
dep(i,n,2){
int w=y+(i<n&&abs(a[i]-a[i+1])==1)-(i<n&&abs(a[i+1]-a[1])==1);
rev(i);
dfs(x+1,w);
rev(i);
if(p)return;
}
}
int main()
{
T=read();
while(T--){
n=read();ans=0;
rep(i,1,n)a[i]=read();
int cnt=0;
rep(i,1,n-1)if(abs(a[i]-a[i+1])>1)cnt++;
while(true){
p=0;
dfs(0,cnt);
if(p)break;
ans++;
//cout<<ans<<endl;
}
cout<<ans<<endl;
}
return 0;
}