C++14(g++5.4) 解法, 执行用时: 277ms, 内存消耗: 376K, 提交时间: 2019-05-22 22:55:23

#include<cstdio>
#include<algorithm>
using namespace std;
struct number
{
	int x,w;
	bool operator <(number y) const
	{
		return x<y.x;
	}
}a[51];
int n;
int ans;
inline void solve(int x,int tot)
{
	if(tot==0&&a[1].x==1)
	{
		ans=min(ans,x);
		return ;
	}
	int i,j,t,cont;
	for(i=2;i<=n;i++)
	{
		cont=tot;
		if(i<n)
			cont-=(abs(a[i].x-a[i+1].x)!=1)-(abs(a[1].x-a[i+1].x)!=1);
		if(x+cont<ans)
		{
			t=i/2;
			for(j=1;j<=t;j++)
				swap(a[j],a[i-j+1]);
			solve(x+1,cont);
			for(j=1;j<=t;j++)
				swap(a[j],a[i-j+1]);
		}
	}
}
int main()
{
	scanf("%d",&n);
	int i;
	for(i=1;i<=n;i++)
	{
		scanf("%d",&a[i].x);
		a[i].w=i;
	}
	sort(a+1,a+1+n);
	for(i=1;i<=n;i++)
		a[a[i].w].x=i;
	ans=2*n;
	int tot=0;
	for(i=2;i<=n;i++)
		tot+=abs(a[i].x-a[i-1].x)!=1;
	solve(0,tot);
	printf("%d\n",ans);
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 252ms, 内存消耗: 376K, 提交时间: 2019-03-09 17:49:53

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
int ans,n,a[58],w[58];
void solve(int x,int tot)
{
	if(!tot && a[1]==1){ans=min(ans,x);return;}
	for(int i=2,t,cont;i<=n;i++)
	{
		cont=tot;
		if(i<n)cont-=(abs(a[i]-a[i+1])!=1)-(abs(a[1]-a[i+1])!=1);
		if(x+cont<ans)
		{
			t=i/2;
			for(int j=1;j<=t;j++)swap(a[j],a[i-j+1]);
			solve(x+1,cont);
			for(int j=1;j<=t;j++)swap(a[j],a[i-j+1]);
		}
	}
}
inline bool cmp(int x,int y){return a[x]<a[y];}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);w[i]=i;
	}
	sort(w+1,w+1+n,cmp);
	for(int i=1;i<=n;i++)a[w[i]]=i;
	int tot=0;ans=2*n;
	for(int i=2;i<=n;i++)tot+=abs(a[i]-a[i-1])!=1;
	solve(0,tot);
	printf("%d\n",ans);
	return 0;
}