题目大意：问从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;
}
