可以bfs,不建议dfs。代码如下:
```cpp
#include<bits/stdc++.h>
using namespace std;
int a[10000001],step[10000001],ss[10000001],b[201],n,head,tail,used[201];
int main(){
cin>>n;
for(int i=1;i<=n;i++){
scanf("%d",&b[i]);
}
a[1]=1;
step[1]=0;
ss[1]=1;
head=0;
tail=1;
used[1]=1;
while(head!=tail){
head++;
for(int i=a[head]+1;i<=n;i++){
if(used[i]==0 && (b[i]-b[a[head]])<=ss[head]){
used[i]=1;
step[++tail]=step[head]+1;
a[tail]=i;
ss[tail]=1;
}
if((b[i]-b[a[head]])>ss[head]) break;
}
if(a[head]!=1){
a[++tail]=a[head]-1;
ss[tail]=ss[head]*2;
step[tail]=step[head]+1;
}
if(a[head]==n){
cout<<step[head];
return 0;
}
}
cout<<-1;
return 0;
}
```
by EnochWenzhou @ 2018-10-07 22:32:33
@[EnochWenzhou](/space/show?uid=40262) 你为啥要手打queue啊,现成的STL多好用
by NaCly_Fish @ 2018-10-07 23:14:35
都差不多的,如果是小根堆还是会用的
by EnochWenzhou @ 2018-10-08 00:39:51
dfs的话
或许可以试试迭代加深算法?
by Rainy_chen @ 2018-10-08 07:11:21
qp
by 1_plus_1_equal_5 @ 2023-07-13 12:00:11