Sgu/157

By mx 此题n的范围很小，可以打表，但打个三两个小时也不是办法，用以下方法可以几秒钟至十几秒钟出结果（本地测n=13时11秒多出结果）。 注意到每种可行状态都可以由另一种可行状态以以下的变换而得出： ①找到给定范围内的Ai，使得Ai=Ai-1 +1。 ②将空位与Ai交换。 (其实就是题目中的变换的逆变换) 所以只要从终态开始，不断以上述变换扩展，每次扩展得到的值必为可行方案。容易证明每种可行状态只有一种变换方案达到终态（因为每次只有一种移动方法），反过来可知，每种状态只会被扩展一次，所以连判重都不用。 下列程序当n≥10时打表，n<10时搜索。搜索本身就可以用来打表。

//by mx
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXN 13
#define MAX(x,y) ((x)>(y)?(x):(y))
#define ABS(x) (MAX(x,-(x)))
#define MIN(x,y) ((x)<(y)?(x):(y))
#define oo 1e9
#define R return
long n,a[MAXN+5]={0},ans=0,place;
void init()
{
	long i;
	scanf("%ld",&n);
	if (n==13) ans=118515434;
	else if (n==12) ans=12966093;
	else if (n==11) ans=1548222;
	else if (n==10) ans=203173;
	place=n;
	for (i=1;i<=n;i++)
	    a[i]=i;
	R;
}
void solve()
{
	long i,t=place;
	ans++;
	for (i=1;i<=n;i++)
	{
		if (i!=place&&a[i]==a[i-1]+1)
		{
			a[place]=a[i];
			a[i]=n;
			place=i;
			solve();
			place=t;
			a[i]=a[place];
			a[place]=n;
		}
	}
	R;
}
void output()
{
	printf("%ld\n",ans);
	R;
}
int main()
{
	init();
	if (n<10) solve();
	output();
	R 0;
}

/by Logic
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=20,N=14;
int n,p[maxn],ans=0;
void dfs(int emp)
{
	int i,j,p0[maxn],z=0;
	memcpy(p0,p,sizeof(p));
	//for(i=1;i<=N;i++) printf("%d ",p[i]); printf("\n");
	ans++;
	for(i=N-n;i<N;i++)
	{
		if(p[i]==p[i+1]-1)
			swap(p[i+1],p[emp]),dfs(i+1);
		memcpy(p,p0,sizeof(p));
	}
}
int main()
{
	int i;
	for(i=1;i<N;i++)
		p[i]=i;
	p[N]=0;
	scanf("%d",&n);
	if(n==11) ans=1548222;
	else if(n==12) ans=12966093;
	else if(n==13) ans=118515434;
	else dfs(14);
	printf("%d",ans);
	return 0;
}