记录编号	232466	评测结果	AAAAAAAAAA
题目名称	[UVA 11163]豹王	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	4.386 s
提交时间	2016-03-01 15:27:43	内存使用	0.26 MiB

#include<cstdio>
#include<iostream>
using namespace std;
const int SIZEN=41,INF=0x7fffffff/8;
int go[4][4]={{-3,-1,4,-4},{1,3,4,-4},{1,-1,4,-4},{1,-1,4,-4}};
int g[SIZEN][SIZEN];
void prepare()
{
	for(int i=1;i<=40;i++) for(int j=1;j<=40;j++) g[i][j]=INF;
	for(int i=1;i<=40;i++) for(int j=0;j<4;j++) g[i][i+go[i%4][j]]=1;
	for(int i=1;i<=40;i++) g[i][i]=0;
	for(int k=1;k<=40;k++)for(int i=1;i<=40;i++)for(int j=1;j<=40;j++) g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
}
int N,T=0,a[SIZEN],pos;
bool read()
{
	scanf("%d",&N);
	if(!N) return 0;
	T++;
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]==1) pos=i;
	}
	return 1;
}
int ans=0;
bool dfs(int deep,int dabo,int now,int fa)
{
	if(dabo<=0) return 1;
	if(deep+dabo>ans) return 0;
	for(int i=0;i<4;i++)
	{
		int x=now+go[now%4][i];
		if(x==fa||x<1||x>N) continue;
		int kk=dabo-g[x][a[x]]+g[now][a[x]];
		if(kk<0) return 1;
		a[now]=a[x];a[x]=1;
		if(dfs(deep+1,kk,x,now)) return 1;
		a[x]=a[now];a[now]=1;
	}
	return 0;
}
void work()
{
	//printf("Set ");
	//printf("%d",T);
	//printf(":\n");
	int dabo=0;//估计函数
	for(int i=1;i<=N;i++) dabo+=g[i][a[i]];
	dabo-=g[pos][1];
	//cout<<g[4][1]<<endl;
	for(ans=0;ans<=INF;ans++)
	{
		//cout<<T<<" "<<ans<<endl;
		if(dfs(0,dabo,pos,-1)) break;
	}
	printf("%d\n",ans);
}
int main()
{
	freopen("uva11163.in","r",stdin);
	freopen("uva11163.out","w",stdout);
	prepare();
	while(read()) work();
	return 0;
}