POJ3460 Booksort IDA*

题目链接

http://poj.org/problem?id=3460

分析

最终状态每本书都有正确后继，每次操作最多使三本书由后继错误变为后继正确；

设某状态有 t o t tot tot 本书后继错误，则未来最少要操作 ⌈ t o t 3 ⌉ \lceil {tot \over 3} \rceil ⌈3tot​⌉ 次。

搜索树深度小，以此为估价函数跑IDA*即可。

AC代码

#include <cstdio>
#include <cstring>

inline int read() {
	int num = 0;
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9')
		num = num * 10 + c - '0', c = getchar();
	return num;
}

const int maxn = 20;

int n, d, a[maxn], b[maxn];

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

inline void change(int l, int r, int e) {
	int p = l;
	for (int i = r + 1; i <= e; ++i) b[p++] = a[i];
	for (int i = l; i <= r; ++i) b[p++] = a[i];
	for (int i = l; i <= e; ++i) a[i] = b[i];
}

int dfs(int done) {
	int tot = wrong();
	if (3 * done + tot > 3 * d) return 0;
	if (!tot) return 1;
	int tmp[maxn];
	memcpy(tmp, a, sizeof(tmp));
	for (int l = 1; l < n; ++l)
		for (int r = l; r < n; ++r)
			for (int e = r + 1; e <= n; ++e) {
				change(l, r, e);
				if (dfs(done + 1)) return 1;
				memcpy(a, tmp, sizeof(a));
			}
	return 0;
}

int main() {
	int t = read();
	while (t--) {
		n = read();
		for (int i = 1; i <= n; ++i) a[i] = read();
		for (d = 0; d <= 4; ++d)
			if (dfs(0)) {
				printf("%d\n", d);
				break;
			}
		if (d == 5) printf("5 or more\n");
	}
	return 0;
}