题面
分析
显然答案有单调性，可以二分答案，设当前二分值为g，根据题意我们可以求出跳跃长度的范围[l,r]
考虑DP
子状态： dp[i]表示跳到第i个点时的最大和
状态转移方程 \(dp[i]=max(dp[i],dp[j]+a[i]) (j \in [1,n),x[i]-x[j] \in [l,r])\)
初始值：dp[0]=0 （把起点看成第0号点，权值和坐标都为0）
直接转移的时间复杂度是\(O(n^2)\)
由于此题数据水，\(O(n^2logn)\)可以卡过
（相信热爱学习，不屑于打暴力的你一定会继续往下看的）
观察状态转移方程，发现满足条件的j一定在某个区间内，且区间在不断移动，类似“滑动窗口问题”，可建立一个单调队列
另外，j存在决策单调性，即i增加时，j一定也不断增加，不会再减小（例如对于i=1时我们求出满足条件的最大j，i=2时满足条件的j一定比i=1时的j更大）
因此，每次循环时j不必重置成0，这样可显著减少时间
然后维护单调队列
对于每个i，我们将满足条件（与i距离>l)的dp[j]不断加入队尾，并同时维护序列的单调性，保证队列从大到小递减，这样队头的答案一定最优
接着处理不合格的情况，即弹出队头与i距离>r的值
现在队头就是满足\(j \in [1,n),x[i]-x[j] \in [l,r]\)的最大dp[j]+a[i]，因此用队头更新dp[i]，i++,继续下一个循环
DP时间复杂度\(O(n)\)
总时间复杂度\(O(nlogn)\)
代码
暴力卡过:
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 500005
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
inline int qread() {
int x=0,sign=1;
char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') sign=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*sign;
}
int n,d;
int k;
int x[maxn];
int a[maxn];
long long dp[maxn];
int check(int g) {
int l0,r0;
memset(dp,-0x3f,sizeof(dp));
long long ans=dp[0];
if(g<d) {
l0=d-g;
r0=d+g;
} else {
l0=1;
r0=d+g;
}
dp[0]=0;
for(int i=1; i<=n; i++) {
for(int j=i-1; j>=0; j--) {
if(x[i]-x[j]<l0) continue;
if(x[i]-x[j]>r0) break;
if(dp[j]+a[i]>dp[i]) dp[i]=dp[j]+a[i];
if(dp[i]>=k) return 1;
}
if(dp[i]>ans) ans=dp[i];
}
if(ans>=k) return 1;
else return 0;
}
int main() {
n=qread();
d=qread();
k=qread();
for(int i=1; i<=n; i++) {
x[i]=qread();
a[i]=qread();
}
dp[0]=0;
x[0]=0;
int l=0,r=1005;
int mid;
int ans=-1;
int t;
while(l<=r) {
mid=(l+r)>>1;
if(check(mid)) {
ans=mid;
r=mid-1;
} else l=mid+1;
}
printf("%d\n",ans);
}
//Dedicated to Selina单调队列：
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 500005
#define INF 0x3f3f3f3f3f3f3f3f
using namespace std;
int n,d;
int k;
int x[maxn];
int a[maxn];
long long dp[maxn];
struct node{
long long v;
int x;
node(){
}
node(long long val,int pos){
v=val;
x=pos;
}
};
struct deque{
int head,tail;
node Q[maxn];
node front(){
return Q[head];
}
node back(){
return Q[tail-1];
}
void push_back(node p){
Q[tail]=p;
tail++;
}
void pop_front(){
head++;
}
void pop_back(){
tail--;
}
bool empty(){
if(head<tail) return 0;
else return 1;
}
deque(){
head=tail=0;
}
void clear(){
head=tail=0;
}
}q;
int check(int g){
int l0,r0;
if(g<d) {
l0=d-g;
r0=d+g;
} else {
l0=1;
r0=d+g;
}
int j=0;
memset(dp,-0x3f,sizeof(dp));
q.clear();
dp[0]=0;
for(int i=1;i<=n;i++){
while(x[i]-x[j]>=l0){//由于j有决策单调性，不必清零
while(!q.empty()&&dp[j]>=q.back().v) q.pop_back();//保证序列单调递减
q.push_back(node(dp[j],x[j]));
j++;
}
while(!q.empty()&&x[i]-q.front().x>r0) q.pop_front();//排除不符合条件的情况
if(q.empty()) dp[i]=-INF;//如果队列为空，说明该点不能到达，直接设为-INF
else dp[i]=q.front().v+a[i];
if(dp[i]>=k) return 1;
}
return 0;
}
int main(){
scanf("%d %d %d",&n,&d,&k);
for(int i=1;i<=n;i++){
scanf("%d %d",&x[i],&a[i]);
}
x[0]=0;
int l=0,r=x[n];
int mid;
int ans=-1;
while(l<=r){
mid=(l+r)>>1;
if(check(mid)){
ans=mid;
r=mid-1;
}else l=mid+1;
}
printf("%d\n",ans);
}
//Dedicated to Selina