CF1341E Nastya and Unexpected Guest(01dfs)

这道题需要将它抽象成图论问题，我们用二维数组f表示走到第i个关键点，绿灯还剩j秒的最小回合数，也就是一轮红绿灯

这样这个问题被抽象成了最短路的问题，因为对于同一个点来说，第一次到达某个状态肯定是最小的，因此能找到最小回合数

这道题还有一个优化是本题的边权是01的，因此可以用双端队列优化一个log

CF1341E Nastya and Unexpected Guest(01dfs)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pll;
const int N=2e5+10;
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
int f[10010][1010];
int d[N];
deque<pll> q;
int main(){
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    int i;
    for(i=1;i<=m;i++){
        cin>>d[i];
    }
    sort(d+1,d+1+m);
    ll ans=1e18;
    int g,r;
    cin>>g>>r;
    memset(f,0x3f,sizeof f);
    f[1][g]=0;
    q.push_front({1,g});
    while(q.size()){
        auto t=q.front();
        int a=t.first;
        int b=t.second;
        q.pop_front();
        if(a>1){
            int dis=d[a]-d[a-1];
            if(b>dis){
                if(f[a-1][b-dis]>f[a][b]){
                    f[a-1][b-dis]=f[a][b];
                    q.push_front({a-1,b-dis});
                }
            }
            else if(b==dis){
                if(f[a-1][g]>f[a][b]+1){
                    f[a-1][g]=f[a][b]+1;
                    q.push_back({a-1,g});
                }
            }
        }
        if(a<m){
            int dis=d[a+1]-d[a];
            if(b>dis){
                if(f[a+1][b-dis]>f[a][b]){
                    f[a+1][b-dis]=f[a][b];
                    q.push_front({a+1,b-dis});
                }
            }
            else if(b==dis){
                if(f[a+1][g]>f[a][b]+1){
                    f[a+1][g]=f[a][b]+1;
                    q.push_back({a+1,g});
                }
            }
        }
    }
    for(i=1;i<=m;i++){
        if(n-d[i]<=g&&f[i][g]!=inf){
            ans=min(ans,1ll*(f[i][g])*(g+r)+n-d[i]);
        }
    }
    if(ans==1e18){
        cout<<-1<<endl;
    }
    else{
        cout<<ans<<endl;
    }
}

View Code

原文链接: https://www.cnblogs.com/ctyakwf/p/13353391.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/369318

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

CF1341E Nastya and Unexpected Guest(01dfs)

相关推荐