本文共 1204 字，大约阅读时间需要 4 分钟。

题目

思路

二分把问题转化为判定性问题，而判定性部分是一个dp，设f[i]为第i个格子跳到的最大得分，dp方程为$f_i=min(f_{i-d+g}to{f}_{i+d-g})+s_i$,这里的min使用单调队列完成即可AC。

注意：元素的入队一定要按顺序来，如果前面某个位置放不进来，那么后面的也不能放进来。

code:

#include
   
    #include
    
     #define ll long longusing namespace std;const ll inf=4e17,e=1;ll n,d,k,ans=-1,x[500001],s[500001],f[500001],l,r,c[500001];bool check(ll g){   	ll l=0,r=1,mx=d+g,mn=max(d-g,e),last=1;	c[l]=0;	for (ll i=1;i<=n;i++)	{   		while (l+1
     
      mx) l++;		if (x[i]-x[c[l]]<=mx&&x[i]-x[c[l]]>=mn) f[i]=f[c[l]]+s[i];		else f[i]=-inf;		if (f[i]>=k) return 1;		while (last<=i&&x[i+1]-x[last]>=mn)		{   			while (l+1<=r&&f[c[r-1]]<=f[last]) r--;			c[r++]=last;			last++;		}	}	return 0;}void read(long long& x){   	x=0;	long long f=1;	char ch=getchar();	while (!isdigit(ch)) (ch=='-')&&(f=-1),ch=getchar();	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();	x*=f;}int main(){   	read(n),read(d),read(k);	for (ll i=1;i<=n;i++) read(x[i]),read(s[i]);	r=1e9;	while (l<=r)	{   		if (check((l+r)>>1))		{   			if (ans==-1||ans>((l+r)>>1)) ans=(l+r)>>1;			r=((l+r)>>1)-1;		}		else		{   			l=((l+r)>>1)+1;		}	}	cout<