讲解 P3957 [NOIP2017 普及组] 跳房子。

首先注意到单调性，考虑二分，然后使用单调队列优化 dp 快速求出最大得分。

思路：

首先发现单调性，灵活性增加 \(x+1\) 的答案肯定不会比增加 \(x\) 的答案更劣。

那么可以二分求 \(g\)，则机器人每次可以移动 \([\max(d-mid,1),d+mid]\) 这个区间内的距离，为了方便，设为 \([l,r]\)。

考虑动态规划求得能走到的最大分数，令 \(dp_i\) 表示走到第 \(i\) 个格子的最大分数，则状态转移方程为：

\[dp_i = s_i + \max\limits_{j=0}^{i-1} [x_i - r \le x_j] [x_j \le x_i - l] dp_j

\]

可以使用单调队列维护：

• 若当前队尾为 \(j\)，且 \(x_j < x_i - r\)，则这个 \(j\) 无法对 \(dp_i\) 造成贡献，直接不断弹出即可。

• 若当前队头为 \(j\)，且 \(x_{j+1} \le x_i - l\)，则这个 \(j+1\) 可以对 \(dp_i\) 造成贡献，不断插入即可。

• 因为要维护最大值，可以使用单调队列。

时间复杂度为 \(O(N \log W)\)。

完整代码：

<code>#include<bits/stdc++.h>

#define Add(x,y) (x+y>=mod)?(x+y-mod):(x+y)

#define lowbit(x) x&(-x)

#define pi pair<ll,ll>

#define pii pair<ll,pair<ll,ll>>

#define iip pair<pair<ll,ll>,ll>

#define ppii pair<pair<ll,ll>,pair<ll,ll>>

#define fi first

#define se second

#define full(l,r,x) for(auto it=l;it!=r;it++) (*it)=x

#define Full(a) memset(a,0,sizeof(a))

#define open(s1,s2) freopen(s1,"r",stdin),freopen(s2,"w",stdout);

using namespace std;

typedef double db;

typedef unsigned long long ull;

typedef long long ll;

bool Begin;

const ll N=5e5+10;

inline ll read(){

ll x=0,f=1;

char c=getchar();

while(c<'0'||c>'9'){

if(c=='-')

f=-1;

c=getchar();

}

while(c>='0'&&c<='9'){

x=(x<<1)+(x<<3)+(c^48);

c=getchar();

}

return x*f;

}

inline void write(ll x){

if(x<0){

putchar('-');

x=-x;

}

if(x>9)

write(x/10);

putchar(x%10+'0');

}

ll n,d,k,l,r,head,tail,ans=-1;

ll a[N],b[N],dp[N],Q[N];

ll check(ll l,ll r){

head=1,tail=0;

ll sum=0,x=1,y=0;

for(int i=1;i<=n+1;i++){

if(i>1)

dp[i]=-1e18;

while(a[y+1]<=a[i]-l&&y<=n){

y++;

while(dp[y]>dp[Q[tail]]&&tail>=head)

tail--;

if(dp[y]>=-1e18)

Q[++tail]=y;

}

while(a[x]<a[i]-r&&x<=n){

if(Q[head]==x)

head++;

x++;

}

if(tail>=head)

dp[i]=b[i]+dp[Q[head]];

sum=max(sum,dp[i]);

}

return sum;

}

bool End;

int main(){

//open("A.in","A.out");

n=read(),d=read(),k=read();

for(int i=1;i<=n;i++){

a[i+1]=read();

b[i+1]=read();

}

l=0,r=1e9;

while(l<=r){

ll mid=(l+r)>>1;

if(check(max(d-mid,1ll),d+mid)>=k){

r=mid-1;

ans=mid;

}

else

l=mid+1;

}

write(ans);

cerr<<'\n'<<abs(&Begin-&End)/1048576<<"MB";

return 0;

}