太久了，稍有遗忘
```
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long f[500005],a[500005][2],n,d,k,ok,lpos,rpos;
bool check(int g)
{
lpos = d-g;//跳的最短距离
rpos = d+g;//跳的最长距离
if(lpos<=0)
lpos = 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]<lpos) continue;
if(a[i][0]-a[j][0]>rpos) break;
f[i]=max(f[i],f[j]+a[i][1]);
if(f[i]>=k)
return 1;
}
}
return 0;
}
int main()
{
int i,ans=-1,l,r,m;
scanf("%lld%lld%lld",&n,&d,&k);
for(i=1; i<=n; i++)
scanf("%lld%lld",&a[i][0],&a[i][1]);
l=0, r=1005;
m=(l+r)/2;
while(l<=r) // 二分答案
{
if(check(m))
{
ans=m;
r=m-1;
}
else
{
l=m+1;
}
m=(l+r)/2;
}
cout<<ans;
return 0;
}
```
by 治涨的馒头 @ 2019-03-27 18:40:29
我只是个蒟蒻
by 治涨的馒头 @ 2019-03-27 18:40:46
@[gjm2005](/space/show?uid=93382)
记住这道题，顺便%一下djq
```cpp
#include <bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<(b);i++)
#define per(i,a,b) for(register int i=(b);i>=(a);i--)
#define For(i,a,b) for(register int i=(a);i<=(b);i++)
#define Forenska(it,c) for(register __typeof(c.begin()) it=c.begin();it!=c.end();it++)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define sqr(x) ((x)*(x))
#define lowbit(x) ((x)&(-x))
using namespace std;
typedef long long LL;
typedef pair<int,int> Pair;
typedef vector<int> vec;
const long double PI=3.14159265358979323846264338327950288;
const LL INFLL=0x3f3f3f3f3f3f3f3f;
const int INF=0x3f3f3f3f;
int read()
{
int x=0;
char ch=' ';
bool flag=false;
while(!isdigit(ch))
{
if(ch=='-')flag=true;
ch=getchar();
}
while(isdigit(ch))
{
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return flag?-x:x;
}
int n,d,k;
const int MAX_N=500005;
int x[MAX_N],s[MAX_N];
LL dp[MAX_N];
bool check(int g)
{
For(i,1,n)dp[i]=-INF;
int L=max(1,d-g),R=d+g,j=0;
deque <int> q;
For(i,1,n)
{
while(x[i]-x[j]>=L && j<i)
{
while(!q.empty() && dp[q.back()]<dp[j])q.pop_back();
if(dp[j]>-INF)q.push_back(j);
j++;
}
while(!q.empty() && x[i]-x[q.front()]>R)q.pop_front();
if(!q.empty())dp[i]=dp[q.front()]+s[i];
}
For(i,1,n)if(dp[i]>=k)return true;
return false;
}
int main()
{
n=read(),d=read(),k=read();
For(i,1,n)x[i]=read(),s[i]=read();
int lb=0,ub=INF;
while(lb<ub)
{
int mid=(lb+ub)/2;
if(check(mid))ub=mid;
else lb=mid+1;
}
cout<<lb<<endl;
return 0;
}
```
by Smile_Cindy @ 2019-03-27 18:44:35
谢谢啦，已经对了
by _gjm2005_ @ 2019-03-27 20:54:09
@[gjm2005](/space/show?uid=93382)
怎么改的？help
by sunxiaofan @ 2019-09-14 17:25:58