题目

分析

get一下IDA*的技巧，感觉总体来说不难，主要是剪枝比较难想。

这是lrj的代码，比较通俗易懂，关键就是选定一个区间再取出来，插入到一个位置，接下来转移到这个状态。

代码

#include <bits/stdc++.h>

using namespace std;

const int maxn=10;

int n,a[maxn];

bool is_sorted()

{

	for(int i=0;i<n-1;i++)

		if(a[i]>=a[i+1]) return false;

	return true;

}

int h()

{

	int cnt=0;

	for(int i=0;i<n-1;i++)

		if(a[i]+1!=a[i+1]) cnt++;

	if(a[n-1]!=n) cnt++;

	return cnt;

}

bool dfs(int d,int maxd)

{

	if(d*3+h() > maxd*3) return false;

	if(is_sorted()) return true;

	int b[maxn],olda[maxn];

	memcpy(olda,a,sizeof(a));

	for(int i=0;i<n;i++)

	for(int j=i;j<n;j++)

	{

		//cut

		int cnt=0;

		for(int k=0;k<n;k++)

			if(k<i || k>j) b[cnt++]=a[k];

		//insert

		for(int k=0;k<=cnt;k++)

		{

			int cnt2=0;

			for(int p=0;p<k;p++) a[cnt2++]=b[p];

			for(int p=i;p<=j;p++) a[cnt2++]=olda[p];

			for(int p=k;p<cnt;p++) a[cnt2++]=b[p];

			if(dfs(d+1,maxd)) return true;

			memcpy(a,olda,sizeof(a));

		}

	}

	return false;

}

int solve()

{

	if(is_sorted()) return 0;

	int max_ans=5;

	for(int maxd=1;maxd<max_ans;maxd++)

		if(dfs(0,maxd)) return maxd;

	return max_ans;

}

int main()

{

	int kase=0;

	while(scanf("%d",&n)==1 && n)

	{

		for(int i=0;i<n;i++) scanf("%d",&a[i]);

		printf("Case %d: %d\n",++kase,solve());

	}

	return 0;

}

巴特西

【UVa】11212 Editing a Book（IDA*）

题目

分析

代码

最新文章

热门文章