uva11212 Editing a Book启发状态搜索 博客分类： 算法题

#include<iostream>
#include<vector>
#include<ctime>
#include<algorithm>
#include<cstdio>
using namespace std;
int n, maxd;

int wrongn(int *p, int a, int b) {
	int t = 0;
	for (int i = a; i < b; i++) {
		if (p[i + 1] - p[i] != 1) t++;
	}
	return t;
}

bool dfs(int h, int act, int *perm) {
	int i, j, st, ed, k, a, b, temp[12];
	/*if (!wrongn(perm, st, ed ))
	if (perm[st] - 1 == perm[perm[st] - 1] || perm[ed] + 1 == perm[perm[ed] + 1])
	return 0;//不拆分连续数字
	*/
	if (act--) {
		temp[0] = temp[n + 1] = 0;
		for (st = 1; st <= n; st++)
			for (ed = st + 1; ed <= n + 1; ed++) {
				for (k = 1; k <= n + 1; k++) {
					if (k > ed) {
						j = 1;
						for (i = 1; i < st; i++) temp[j++] = perm[i];
						for (i = ed; i<k; i++) temp[j++] = perm[i];
						for (i = st; i < ed; i++) temp[j++] = perm[i];
						for (i = k; i <= n; i++) temp[j++] = perm[i];
					}
					else if (k < st) {
						j = 1;
						for (i = 1; i < k; i++) temp[j++] = perm[i];
						for (i = st; i < ed; i++) temp[j++] = perm[i];
						for (i = k; i<st; i++) temp[j++] = perm[i];
						for (i = ed; i <= n; i++) temp[j++] = perm[i];
					}
					else continue;

					a = wrongn(temp, 1, n);
					if (!a) return true;
					if (a > h) continue;
					if (a > 3 * act) continue;
					if (dfs(a, act, temp)) {
						//cout << i << ' ' << i + j << "->" << k << endl;
						return true;
					}
				}

			}
	}
	return 0;
}

void solve(int T) {
	int i, j, k, h, ss;
	int perm[12];
	perm[0];
	for (i = 1; i <= n; i++)
		scanf("%d", &perm[i]);
	perm[0] = perm[n + 1] = 0;
	h = wrongn(perm, 1, n);
	if (!h) {
		printf("Case %d: 0\n", T); return;
	}
	for (maxd = 1; ; maxd++) {
		if (h > 3 * maxd) continue;
		if (dfs(h, maxd, perm)) {
			printf("Case %d: %d\n", T, maxd);
			return;
		}
	}
}

int main()
{
	int T = 0;
	//clock_t start, stop;
	//start = clock();
	while (scanf("%d", &n) == 1 && n) {
		solve(++T);
	}
	//stop = clock();
	//printf("Use Time:%ld\n", (double)(stop - start));

	return 0;
}
//system("pause");

/*
2
2 1
6
2 4 1 5 3 6
5
3 4 5 1 2
9
9 8 7 6 5 4 3 2 1
0

*/