UVA-1374 旋转游戏 题解答案代码 算法竞赛入门经典第二版

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;
}