竞赛讨论区 > 求助E题反复横跳和F题图题目的思路,E题已会,求助F题大佬

求助E题反复横跳和F题图题目的思路,E题已会,求助F题大佬

头像
黯灭拍拍熊
编辑于 2021-04-25 13:31:00 APP内打开
赞 0 | 收藏 0 | 回复6 | 浏览447
求助,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条回帖

回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐