好端端的一道搜索题目，，，硬生生的被我弄成了乱搞题，，，枚举当前的maxd，深搜结果，然而想到的剪枝方法都没有太好的效果，，，最后用一个贪心乱搞弄出来了，，，
贪心：每次必用上一次做出来的数字与其他数字组合得到结果。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <vector> 5 //#define debug 6 int n; 7 int maxd; 8 int v1[1000]; 9 long long c[100]; 10 11 bool check(void) { 12 for (int i = 1; i <= maxd + 1; i++) 13 if (v1[i] == n) return 1; 14 return 0; 15 } 16 17 18 bool h(int d) { 19 if (v1[d] * c[maxd - d + 1] < n) return 1; 20 return 0; 21 } 22 23 bool dfs(int d) { 24 if (d == maxd + 1) { 25 #ifdef debug 26 for (int i = 0; i < v1.size(); i++) printf("%d ", v1[i]); 27 printf(" "); 28 #endif 29 if (check()) return 1; 30 return 0; 31 } 32 if (h(d)) return 0; 33 for (int i = 1; i <= d; i++) { 34 v1[d+1] = v1[d] + v1[i]; 35 if (dfs(d + 1)) return 1; 36 v1[d+1] = abs(v1[d] - v1[i]); 37 if (dfs(d + 1)) return 1; 38 v1[d+1] = 0; 39 } 40 return 0; 41 } 42 43 int main () { 44 c[0] = 1; 45 for (int i = 1; i <= 60; i++) c[i] = c[i-1] * 2; 46 while (scanf("%d", &n) == 1 && n) { 47 memset(v1, 0, sizeof(v1)); 48 v1[1] = 1; 49 for (maxd = 0; ; maxd++) { 50 if (dfs(1)) { 51 printf("%d ", maxd); 52 break; 53 } 54 } 55 } 56 return 0; 57 }