题解 | #长跑#

读题

由于每个补给点都能补满体力，所以只需考虑是否在某个补给点停下。

这道题使用数据规模不大，剪枝思路有限，所以使用dfs暴力递归即可。这种方法和队列没有什么关系。

int N,L,Smax,m;
struct shop{
    int pos,c;
    inline bool operator<(shop&y){
        return this->pos < y.pos;
    }
};
vector<shop> shops;

bool canget(int inow,int mnow){
    if(Smax >= L-shops[inow].pos){
        return true;
    }else{
        for(int k=inow+1;k<=N;++k){
            if(shops[k].pos-shops[inow].pos>Smax){
                break;
            }else{
                if(mnow>=shops[k].c){
                    if(canget(k,mnow-shops[k].c)){
                        return true;
                    }
                }
            }
        }
        return false;
    }
    
}

//Extern vars are above
int main(){
#ifdef LOCAL
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif // LOCAL   
    
    while(cin>>N>>L>>Smax>>m){
        shops.clear();
        shops.push_back({0,0});
        int temp,temc;
        for(int iN=1;iN<=N;++iN){
            cin>>temp>>temc;
            shops.push_back({temp,temc});
        }
        sort(shops.begin(),shops.end());
        
        if(canget(0,m)){
            printf("Yes\n");
        }else{
            printf("No\n");
        }
    }
}