UVa 11212 편집 서적 편집 도서 교체 심화

주요 한 사고방식 은 자서 에서 나 온 것 이다. 교체 가 깊 어 지 는 알고리즘 을 이용 하여 한 층 한 층 아래로 검색 하고 교체 가 깊 어 지 는 주 체 는 bfs 이다.그래서 매번 의 최대 검색 층수 maxd 는 0 에서 maxd - 1 층 까지 답 을 찾 지 못 한 것 을 의미 하기 때문에 교체 깊이 는 maxd - 1 층 을 바탕 으로 한 층 (maxd 층) 을 더 찾 은 것 과 같다. 이것 은 전형 적 인 bfs 로 가장 짧 은 길 등 문 제 를 구 하 는 데 사용 된다.
이 문제 에서 n 의 범 위 는 1 에서 9 이기 때문에 검색 층수 의 범 위 는 1 에서 8 이다.
평가 함수 h () 는 이렇게 확 정 됩 니 다. 매번 잘라 내기 / 붙 여 넣 기 는 최대 세 개의 수의 후계 (독자 가 스스로 검증 할 수 있 습 니 다) 를 바 꿉 니 다. 즉, 한 층 을 검색 할 때마다 최대 세 개의 숫자의 후계 가 오류 에서 정확 해 지기 때문에 (maxd - 현재 층수) * 3 < 현재 오류 의 후계 수 는 가 지 를 잘라 야 합 니 다.

#include 
#include 
int a[30];
int kase = 1;
int n;

int hh()
{
	int cur = 0;
	for(int i = 1; i < n; i++)
		if(a[i+1] != a[i] + 1)  cur++;
	if(a[n] != n)  cur++;
	return cur;
}

bool dfs(int cur, int maxd)
{
	int h = hh();
	if(cur == maxd)  return h == 0;
	if(cur < maxd)  if(3*cur + h > 3*maxd + 1)  return false;
	int olda[30];
	int b[30];
	memcpy(olda, a, sizeof(a));
	for(int i = 1; i <= n; i++)                               //       
	for(int j = i; j <= n; j++)                               //       
	{
		int now = 1;
		for(int k = 1; k <= n; k++)
		if(k < i || k > j)  b[now++] = a[k];
		for(int d = 1; d <= now; d++)                     //       a[i..j],      b[1..now-1],  a[i..j]         b[1],b[2],..,b[now]   。
		{
			int now2 = 1;
			int ii = i;
			for(int p = d; p < d+j-i+1; p++)  a[p] = olda[ii++];
			for(int p = 1; p < d; p++)  a[p] = b[now2++];
			for(int p = d+j-i+1; ; p++)
			{
				//printf("p = %d i = %d j = %d n = %d
",p,i,j,n);	
				a[p] = b[now2++]; 
				if(now2 > n-(j-i+1)) break;
			}
			if(dfs(cur+1, maxd)) return true;         //    
			memcpy(a, olda, sizeof(a));               //  a  
		}
	}
	return false;
}

int solve()
{
	int maxd_max = 8;
	for(int maxd = 0; maxd < 8; maxd++)
		if(dfs(0, maxd))  return maxd;
	return maxd_max;
}


int main()
{
	//freopen("ztest.txt","r",stdin);
	//freopen("zans.txt","w",stdout);
	while(scanf("%d",&n) && n)
	{
		for(int i = 1; i <= n; i++)
			scanf("%d",&a[i]);
		printf("Case %d: %d
", kase++, solve());
	}
	return 0;
}