思路

设$f[i]$表示跳到第格的最高得分，那么$f[i]$肯定是从它前面那些能够跳到的格子里面得分最高的那个格子跳过来的，可以从$i$号格子前面第一个格子开始查找得分最高的格子，直到超过最大可跳范围为止，把这个区间的最大得分加上自己本身的分数就是第$i$格的最高分数了。

然后再用二分（类似跳石头），直接查找$g$即可。

代码

#include <bits/stdc++.h>
using namespace std;
long long n, d, k, a[500005][2], l, r, le, ri, f[500005], ans = 0;
bool check(long long g)
{
    le = d - g;
    ri = d + g;
    if (le <= 0)
        le = 1;
    memset(f, -127, sizeof(f));
    f[0] = 0;
    for (int i = 1; i <= n; i++)
    {
        for (int j = i - 1; j >= 0; j--)
        {
            if (a[i][0] - a[j][0] < le)
                continue;
            if (a[i][0] - a[j][0]>ri)
                break;
            f[i] = max(f[i] ,f[j] + a[i][1]);
            if (f[i] >= k)
                return 1;
        }
    }
    return 0;
}
int main()
{
    scanf("%lld%lld%lld",&n,&d,&k);
    for (int i = 1; i <= n; i++)
        scanf("%lld%lld", &a[i][0], &a[i][1]);
    l = 0, r = 1000, ans = 0;
    long long mid = (l + r) / 2;
    while (l <= r)
    {
        if (check(mid))
        {
            ans = mid;
            r = mid - 1;
        }
        else
            l = mid + 1;
        mid = (l + r) / 2;
    }
    cout << ans;
    return 0;
}

代码已AC，求赞

#include <bits/stdc++.h> 
#define LL long long 
#define INF 0x7f7f7f7f 
#define MAXN 500005
using namespace std ; 
LL n , k , d , x[MAXN] , s[MAXN] , q[MAXN] , h , t , f[MAXN] ;
bool check( LL g )
{
   LL L = max( (LL)1 , d-g ) , R = d+g , whe=1 ; 
   for(int i=1; i<=n; i++) f[i] = -INF ;
   h = 1 ; t = 0 ; 
   for(int i=1; i<=n; i++)
   {
      if( x[i] > R ) break;
      if( x[i] < L ) continue ;
      f[i] = s[i] ; 
   }
   for(int i=1; i<=n ;i++)
   {
      while( h<=t && x[q[h]] < x[i]-R ) h++ ; 
      while( x[whe] <= x[i]-L ) 
      {
        whe++ ;
	    if( f[whe-1] ==  -INF ) continue ; 
	    if( x[whe-1] < x[i]-R ) continue ; 
	    while( h<=t && f[q[t]] <= f[whe-1] ) t-- ; 
	    q[++t] = whe-1 ; 
      }
      if( h<=t )  f[i] =  max( f[i] , f[q[h]]+s[i] )   ; 
      if( f[i] >= k ) return 1 ; 
    } return 0 ;
}
int main() 
{
    LL l = 0 , r = 0 , mid , tot=0 , Ans  ;
    cin >> n >> d >> k ;
    for(int i=1; i<=n; i++)
      cin >> x[i] >> s[i] , r = max( r , x[i] ) , tot+= ( s[i] > 0 ? s[i] : 0 ) ; 
   if( tot < k ) 
   {
       cout << "-1" << endl;
       return 0 ;
    }
    while( l<=r ) 
    {
        mid = l+r>>1 ;
        if( check(mid) ) Ans = mid , r = mid-1 ;
	      else l = mid+1 ;
    } 
   cout << Ans << endl;
   return 0 ;
}

AC