雅礼集训1.4 序列

Posted by yjjr's blog on January 1, 2018

标签:迭代加深搜索,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;
}


本文可以转载,但必须附上原文链接,否则你会终生找不到妹子!!!欢迎关注我的CSDN: ahyjjr