GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

由于书上给了思路，所以做起来并不难。

即使超时，因为数据量不大（1000个）， 我们也可以直接打表直接返回结果。

但是如果想不打表完成题目，那么就需要使用思路中给出的各种优化方案，不然很容易超时。

我一开始用set作为存储已存在的数字，但还是超时，后面改成用数组存储AC了。

AC代码

#include<stdio.h>
#include<string.h>
#include<math.h>

int n, maxCount;
int setArr[1010];
int maxV;

int getMin(int a, int b) {
	if(a > b) return b;
	return a;
}

// 递归遍历 
bool dfs(int count, int pre, int subCount) {
	if(pre == n) return true;
	if(count >= maxCount) return false;
	if(maxV * (1 << (maxCount - count)) < n) return false;
	if(subCount > 2) return false;
	int value, preMaxV, i;
	if(pre < n) {
		for(i = getMin(maxV, n); i > 0; --i) {
			if(!setArr[i]) continue;
			value = i + pre;
			if(value > 1000 || (value > n && maxV > n)) continue;
			if(setArr[value]) continue;
			setArr[value] = 1;
			preMaxV = maxV;
			if(value > maxV) maxV = value;
			if(dfs(count+1, value, subCount)) return true;
			setArr[value] = 0;
			maxV = preMaxV; 
		}
	}
	if(subCount == 2) return false;
	for(i = maxV; i > 0; --i) {
		if(!setArr[i]) continue;
		value = abs(i - pre);
		if(value == 0 || value > n) continue;
		if(value == n) return true;
		if(setArr[value]) continue;
		setArr[value] = 1;
		if(dfs(count+1, value, subCount + 1)) return true;
		setArr[value] = 0;
	}
	return false;
}

// 初始化 
int computed() {
	if(n == 1) return 0;
	for(maxCount = 1; maxCount < 20; ++maxCount) {
		memset(setArr, 0, sizeof(setArr));
		setArr[1] = 1;
		maxV = 1;
		if(dfs(0, 1, 0)) return maxCount;
	}
}

int main() {
	while(scanf("%d", &n) == 1 && n > 0) {
		printf("%d\n", computed());
	}
	return 0;
}