https://www.luogu.org/problem/P3957
沉迷普及组题无法自拔。
显然二分答案，然后里面套个dp，$f[i]$表示跳到第$i$个格子的最大得分，复杂度$O(n^2logn)$50pts到手。
但是仔细思考就知道$f[i]$只能从它前面一段特定区域的最大的$f$转移过来，并且这个区域是随着$i$往后动的。
滑动窗口石锤，我们就可以维护一个单调队列来做这道题了，复杂度直接变为$O(nlogn)$
……但是即使你想出来了实现也不好写，而且仍然有很多细节需要解决……debug细节花了一个小时多……老龄化实锤。
1.这题只能跳到给定的方块上（最开始我想复杂了结果觉得不可做看了题解才意识到……）
2.注意我们要转移的对象和我们的滑动窗口是有一定距离的，也就是说转移$f[i]$时$f[i-1]$不一定在滑动窗口里，我们就需要另开变量去找哪些在滑动窗口里，详见代码。
3.注意初始化！到不了的格子别忘记初始为-INF，INF要特别大，必要时开long long
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; const int N=5e5+5; const ll INF=1e12; inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X; } struct data{ int x; ll s; }q[N],f[N]; int n,d,k; int x[N],s[N]; bool pan(int g){ ll ans=0;int l=1,r=0; q[++r]=(data){0,0}; for(int i=1,j=1;i<=n;i++){ f[i].s=-INF; if(d-g>x[i])continue; while(l<=r&&(q[l].x+d+g<x[i]))l++; for(;j<i;j++){ if(f[j].x+d+g<x[i])continue; if(f[j].x+d-g>x[i])break; while(l<=r&&f[j].s>=q[r].s)r--; q[++r]=f[j]; } if(l<=r){ f[i]=(data){x[i],q[l].s+s[i]}; ans=max(ans,f[i].s); } } return ans>=k; } int main(){ n=read(),d=read(),k=read(); for(int i=1;i<=n;i++){ x[i]=read();s[i]=read(); } int l=0,r=1e9; while(l<r){ int mid=(l+r)>>1; if(pan(mid))r=mid; else l=mid+1; } if(pan(l))printf("%d ",l); else puts("-1"); return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++