本人是NOIP2017的亲历者，两年前这道题我在考场上随便打了个二分暴力，就草草结束了
如今在做这道题，便能简单的AC了
我采用的思路是二分答案，然后用dp判断答案的可行性。定义f[i]表示到i这个格子最大的分数，如果为一个极小值则可以认为这个点无法到达；x[i]表示i的位置，g表示当前二分的答案。
那么存在状态转移方程：
在这里，我们可以维护一个单调队列，存储对于当前i的决策允许集合，使得队列当中的元素x值递增，f值递减，当i改变时，我们维护单调队列即可。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 typedef long long ll; 7 inline int read() { 8 int ret=0; 9 int op=1; 10 char c=getchar(); 11 while(c<'0'||c>'9') {if(c=='-') op=-1; c=getchar();} 12 while(c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar(); 13 return ret*op; 14 } 15 int n,dis,num; 16 int x[500010],v[500010],q[500010]; 17 ll f[500010]; 18 bool check(int g) { 19 int h=1,t=0; 20 memset(q,0,sizeof(q)); 21 int now=0; 22 int maxx=dis+g; 23 int minn=max(dis-g,1); 24 for(int i=1;i<=n;i++) { 25 while(x[now]<=x[i]-minn) { 26 if(f[now]<=-1e9) { 27 now++; 28 continue ; 29 } 30 while(h<=t&&f[now]>=f[q[t]]) t--; 31 q[++t]=now++; 32 } 33 while(h<=t&&x[q[h]]+maxx<x[i]) h++; 34 if(h<=t) f[i]=f[q[h]]+v[i]; 35 else f[i]=-1e9; 36 if(f[i]>=num) return 1; 37 } 38 return 0; 39 } 40 int main() { 41 n=read(); dis=read(); num=read(); 42 for(int i=1;i<=n;i++) { 43 x[i]=read(); 44 v[i]=read(); 45 } 46 int l=0,r=500000000,ans=-1; 47 while(l<=r) { 48 memset(f,0,sizeof(f)); 49 int mid=l+r>>1; 50 if(check(mid)) { 51 ans=mid; 52 r=mid-1; 53 } 54 else l=mid+1; 55 } 56 if(ans==-1) puts("-1"); 57 else printf("%d ",ans); 58 return 0; 59 }