SP7579 YOKOF - Power Calculus 题解

一道搜索题，搜索需要几步能到达目标预计状态。 记得搜索×的状态和÷的状态。 DFS例题赛高！ emmm细节看代码 ``` #include<bits/stdc++.h> using namespace std; int maxn/*步数最大值*/,n/*输入数字*/,S[50]/*存储数组*/; bool find(int step,int now){//DFS函数 if(step>maxn||now<=0||now<<(maxn-step)<n) return 0;//判断非法状态 if(now==n||now<<(maxn-step)==n) return 1;//记录答案 S[step]=now;//存入数组 for(int i=0;i<=step;i++){ if(find(step+1,now+S[i]))return 1;//DFS乘S[i]的情况 if(find(step+1,now-S[i]))return 1;//DFS除以S[i]的情况 } return 0; } signed main(){ while(scanf("%d",&n)&&n){//读入多组数据 for(maxn=0;!find(0,1);maxn++);//查找最小需求步数 printf("%d\n",maxn);//输出答案 } } ```