跳房子 P3957: 单调队列

#include <bits/stdc++.h>
#define int long long
using namespace std;
constexpr int maxn = 5e5+10;
constexpr int INF = 0x3f3f3f3f3f3f3f3f;int wi[maxn],di[maxn];
int q[maxn];    // 降序单调队列
int dp[maxn];  // dp[i]=跳到i的最大和
// 跳跃范围[i+max(d-x,1),i+d+x]
// 反观状态转移方程：i由前面可以到达它的dp最大值
// dp[i]=max(dp[y] | y \in [i-d-x,i-max(d-x,1)])
int n,d,k;bool chy(int x)//单调队列优化dp
{int dl=max(1LL,d-x);// 跳跃最小距离int dr=d+x;         // 跳跃最大距离fill(dp+2,dp+n+1,-INF);// dp[1]=0int h=1,t=0;int j=1;    // 可能跳到i的最后一个的点下一个点for(int i=2;i<=n;++i){while(di[i]-di[j]>=dl && j<i)// di[j]<i-max(d-x,1)进入队列{if(dp[j]>-1e6) // 1可达j{while(h<=t && dp[q[t]]<dp[j]){--t;}q[++t]=j;}++j;}while(h<=t && di[i]-di[q[h]]>dr) // 队头<i-d-x，弹出头{++h;}if(h<=t) // 队列为空说明1不可达i，不作更新{dp[i]=dp[q[h]]+wi[i];}if(dp[i]>=k)// 提前打断{return 1;}}return 0;
}signed main()
{#ifndef ONLINE_JUDGEfreopen("cjdl.in","r",stdin);freopen("cjdl.out","w",stdout);#endif // ONLINE_JUDGEscanf("%lld%lld%lld",&n,&d,&k);int tal=0;int ma_d=0;++n;wi[1]=0;// 添加起点di[1]=0;for(int i=2;i<=n;++i){scanf("%lld%lld",&di[i],&wi[i]);if(wi[i]>0){tal+=wi[i];}ma_d=max(ma_d,di[i]);}if(tal<k)// -1的特判{printf("-1");return 0;}int l=-1,r=ma_d+1;// 返回r，0是可能解，l要设为-1int mid;while(l<r-1){mid=(r+l)>>1;if(chy(mid)){r=mid;}else{l=mid;}}printf("%lld",r);return 0;
}