NC14570. 长跑
描述
输入描述
本题包含多组数据，每组数据包含N+1行。
第一行输入四个个数字N,L,Maxn,S
接下来N行，每行输入两个数字，Pi，Ci
数据范围：
每个点上边可能有多个补给站(毕竟要货比三家啊)；
0<=N<=2000
0<=L<=20000
0<=Maxn<=20000
0<=S<=2000
1<=Pi<=N
1000<=Ci<=3000
输出描述
每组数据输出一行，如果小明能够跑到终点，那么输出Yes，否则输出No
示例1
输入:
1 1000 500 2000 500 2000 1 1000 500 2000 500 3000
输出:
Yes No
C++(clang++ 11.0.1) 解法, 执行用时: 84ms, 内存消耗: 652K, 提交时间: 2023-07-25 16:12:42
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p[20005];
ll n,l,mx,f,s,x,y;
void dfs(int a,int b){
if(a+mx>=l){
f=1;
return;
}
for(int i=a;i<=a+mx;i++)
if(b>=p[i] && p[i])
dfs(i,b-p[i]);
return;
}
int main(){
while(cin>>n>>l>>mx>>s){
memset(p,0,sizeof p);
f=0;
for(int i=0;i<n;i++)
cin>>x>>y,p[x]=y;
dfs(0,s);
if(f)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
return 0;
}