来一发简单做法
题目链接：SP7579 YOKOF - Power Calculus
题目大意：如何用最少的步数凑出一个次数。
思考一个问题：题干提到的相乘，实际上可以看做同底数幂相乘，底数不变，指数相加，我们只需要维护一个变量指数就可以了。
那么难点就来了，怎么有效的利用中间产物？开个数组 \(num\) 储存，下标就可以是当前用的步数。
我们可以使用迭代加深搜索，每次规定一个步数，能到达目标，就返回一，输出该步数。考虑剪枝，如果从当前局面开始，每次都用最大的两个数相乘，也就是最大的两个指数相加，都不能达到目标的话，就直接返回不可以。
记得处理边界，搜到最后一步，或者一波操作也没能返回可以，就只好返回不可以了！
见代码：
#include<iostream>
#include<cstdio>
using namespace std;
int num[100001], n, dep;
bool dfs(int step,int now){
if(now <= 0 || step > dep || now << (dep - step) < n) return 0;
if(now << (dep - now) == n) return 1;
if(now == n) return 1;
num[step] = now;//储存当前步骤的指数
for(int i = 0;i <= step; i++){
if(dfs(step + 1,now + num[i])) return 1;
if(dfs(step + 1,now - num[i])) return 1;
}
return 0;
}
int main(){
while(1){
cin >> n;
if(n == 0) break;
for(dep = 0; ; dep++){
if(dfs(0,1)) break;
}
cout << dep << endl;
}
return 0;
}