求助E题反复横跳和F题图题目的思路，E题已会，求助F题大佬
求助，E题反复横跳的思路，是动态规划吗?还有F题的思路。。。
E题我用下面这个BFS结果内存爆了。。。
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct node{
int pos,op,step;
node(int pos,int op,int step):pos(pos),op(op),step(step){}
};
int main() {
int s,t;
cin>>s>>t;
if(s == t){
cout<<"0"<<endl;
return 0;
}
int op = 1,step = 1;
vector<int> v;
int sum = 0;
queue<node>q1,q2;
q1.push(node(s,1,1));
int res = 0;
while(!q1.empty()){
res++;
while(!q1.empty()){
node n1 = q1.front();
if(n1.pos == t){
cout<<res-1<<endl;
return 0;
}
q1.pop();
q2.push(node(n1.pos+n1.op*n1.step,n1.op*-1,n1.step*2));
q2.push(node(n1.pos,1,1));
}
swap(q1,q2);
}
return 0;
} 好吧，我终于写出来了。。果然还是BFS，用的是楼下某位大佬提供的思路，用最短路径算法就可，初步体验了下优先队列。。太强了。。
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
struct node{
int dis;
int pos;
node(int dis,int pos):dis(dis),pos(pos){}
bool operator <(const node& tmp)const{
return dis>tmp.dis;
}
};
int main() {
int s,t,step = 1,sum = 0;
cin>>s>>t;
vector<int> v;
//前17个数：0 1 -1 3 -5 11 -21 43 -85 171 -341 683 -1365 2731 -5461 10923 -21845
for(int i = 0;i<17;i++){
v.push_back(sum);
sum+= step;
step *= -2;
}
//为了保证dis数组的下标为正数，s,t都加25000；
s+=25000;t+=25000;
vector<int>dist(60000,INT32_MAX);
vector<int>vis(60000,0);
priority_queue<node> pq; //默认大顶堆，所以结构体重载大于号
pq.push(node(0,s));
while(!pq.empty()){
node node1 = pq.top(); //醉了，队列queue是front，优先队列是top()
pq.pop();
if(node1.dis>dist[node1.pos])
continue;
if(node1.pos == t){
cout<<node1.dis;
break;
}
//对于每个节点加入在该节点重置，后继续跳17步之内的所有节点
//至于该节点继续再本身step基础上再*2跳的节点不考虑，因为之前已经考虑过了,
//那么也就意味着结构体中不需要保存当前节点的step和op！太妙了，哈哈
for(int i = 1;i<17;i++){
int pos = node1.pos+v[i],cost = node1.dis+i+1;
if(pos<0 || pos>50000) break; //防止dist下标越界
if(vis[pos]) continue; //不加这个会超时，太难了。。
if(node1.dis == 0) cost--; //如果是第一个从S出发的节点，需要减1
pq.push(node(cost,pos));
dist[pos] = min(dist[pos],cost);
vis[pos] = 1;
}
}
return 0;
} 