程序员人生 网站导航

UVA - 1374 Power Calculus 迭代深搜

栏目:php教程时间:2015-06-08 08:12:15

题目大意:问从1变到n最少需要多少步。变换规则以下
1.变化进程中的中间结果可以任意使用
2.每次只能挑选两个数进行加减

解题思路:先算1下最少需要多少步,然后在如果在当前步数下没法到达结果的话,就当前步数加1,继续搜索下去

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define maxn 1010 int num[maxn], cnt, n ,MIN_depth; bool dfs(int cur, int depth) { if(depth >= MIN_depth) { if(cur == n) return true; return false; } int MAX = 0; for(int i = 0; i < cnt; i++) MAX = max(MAX,num[i]); if( ((cur + MAX) << (MIN_depth - depth - 1)) < n) return false; for(int i = cnt - 1; i >= 0; i--) { num[cnt++] = cur + num[i]; if(dfs(cur + num[i], depth+1)) return true; cnt--; num[cnt++] = cur - num[i]; if(dfs(cur - num[i],depth+1)) return true; cnt--; } return false; } int main() { while(scanf("%d", &n) == 1 && n) { MIN_depth = 0; int t = 1; while(t < n) { t += t; MIN_depth++; } while(1) { num[0] = cnt = 1; if(dfs(1,0)) break; MIN_depth++; } printf("%d ", MIN_depth); } return 0; }
------分隔线----------------------------
------分隔线----------------------------

最新技术推荐