求助,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; }
全部评论
(6) 回帖