单调队列及单调队列优化DP

首先是单调队列: 

其实单调队列就是一种队列内的元素有单调性（单调递增或者单调递减）的队列，答案（也就是最优解）就存在队首，而队尾则是最后进队的元素。因为其单调性所以经常会被用来维护区间最值或者降低$DP$的维数已达到降维来减少空间及时间的目的。

类似于滑动窗口等,单调队列具有时序性的储存区间最大值或区间最小值,以下为例题:
P1886 滑动窗口 /【模板】单调队列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

P1440 求m区间内的最小值 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

上题均可用滑动窗口模板解决:

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+10;
int n,m,hh,tt,a[N],q[N],k;
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++) cin>>a[i];
    hh=1,tt=0;
    for(int i=1;i<=n;i++){
        while(hh<=tt&&q[hh]<i-k+1) hh++;
        while(hh<=tt&&a[q[tt]]>=a[i]) tt--;
        q[++tt]=i;
        if(i>=k) cout<<a[q[hh]]<<' ';
    }
    cout<<endl;
    hh=1,tt=0;
    for(int i=1;i<=n;i++){
        while(hh<=tt&&q[hh]<i-k+1) hh++;
        while(hh<=tt&&a[q[tt]]<a[i]) tt--;
        q[++tt]=i;
        if(i>=k) cout<<a[q[hh]]<<' ';
    }
    return 0;
}

对于单调队列优化$DP$,在状态转移的时候会发生我们需要转移到一个区间的某一个点上,而在最佳答案的情景下这个点一般为最大值或者最小值,考虑遍历区间复杂度较高,可采用求区间最值方法来确定一个点的位置即可:
P1725 琪露诺 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

对于该题,我们从位置 $0$ 开始,然后在位置 $i$ 时,无非是是从区间 $[i-r,i-l]$ 转移而来,故我们使用单调队列储存 $dp$ 状态在这个区间的最大值即可,区间最大值加上现在位置的贡献即为这个位置状态的贡献,如果从某个位置开始可以直接跳走,即 $i+r>n$ 则从此时开始更新迭代答案即可,这里再解释以下为什么是 $i-l$ 入队,因为我们向前走一步,即 $i变成i+1$, 我们的区间窗口也要滑动,此时新进来的数就是 $i-l$

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e6+10;
int n,l,r,q[N],hh=1,tt,dp[N],a[N],res=-1e18;
signed main(){
    cin>>n>>l>>r;
    for(int i=1;i<=2*n;i++) dp[i]=-1e18;
    for(int i=0;i<=n;i++) cin>>a[i];
    for(int i=l;i<=n;i++){
        while(hh<=tt&&q[hh]<i-r) hh++;
        while(hh<=tt&&dp[q[tt]]<dp[i-l]) tt--;
        q[++tt]=i-l,dp[i]=dp[q[hh]]+a[i];
        if(i+r>n) res=max(res,dp[i]);
    }
    cout<<res;
}

P3957 [NOIP2017 普及组] 跳房子 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目要求最小金钱数目,则可以考虑用二分,因为我们可以具有区间灵活度,花费金钱越大灵活度越大,所以最终的答案一定是递增的,故可以使用二分答案

接下来是 $check$ 函数,考虑使用单调队列DP,由于每次进行的步数都不一样,所以此时进行状态转移即可得到最优解,首先确定每次跳跃的区间左端点和右端点,然后进行遍历,设置一个变量 $j$,表示最后一个加入队伍的编号,对于 $i$ 之前的距离,如果 $i和j$ 之间相差的距离满足跳跃区间,那么可以考虑是否加入队列,此时单调队列更新完成,更新 $dp[i]$ 即可,由于游戏随时可以停止,所以要时刻判断

#include<bits/stdc++.h>
#define int long long 
using namespace std;
const int N=2e6+10;
pair<int,int>robot[N];
int n,d,k,dp[N],q[N],sum;
bool check(int g){
    int l,r,hh=1,tt=0,j=0;
    if(g>=d) l=1,r=d+g;
    else l=d-g,r=d+g;
    for(int i=1;i<=n;i++) dp[i]=-2e9,q[i]=0;
    dp[0]=0,q[0]=0;
    for(int i=1;i<=n;i++){
        while(robot[i].first-robot[j].first>=l&&j<i){
            if(dp[j]>-2e9){
                while(hh<=tt&&dp[q[tt]]<=dp[j]) tt--;
                q[++tt]=j;
            }
            j++;
        }
        while(hh<=tt&&robot[i].first-robot[q[hh]].first>r) hh++;
        if(hh<=tt) dp[i]=dp[q[hh]]+robot[i].second;
        if(dp[i]>=k) return true;
    }
    return false;
}
signed main(){
    cin>>n>>d>>k;
    for(int i=1;i<=n;i++){
        int a,b; cin>>a>>b;
        robot[i]={a,b};
    }
    int l=1,r=1e9;
    while(l<r){
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<(r==1e9?-1:r);
}