luogu P3572 [POI2014]PTA-Little Bird |单调队列

从1开始，跳到比当前矮的不消耗体力，否则消耗一点体力，每次询问有一个步伐限制，求每次最少耗费多少体力

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e6+10;
#define int long long
int a[N],dp[N],q[N],l,r=1;
int n,m,k;
inline void in(){
    cin>>n;
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    cin>>m; 
}
signed main(){
    in();
    while(m--){
        scanf("%lld",&k);
        l=r=1,q[r]=1;
        for(int i=2;i<=n;i++){
            while(l<=r&&i-q[l]>k)l++;
            if(a[q[l]]>a[i])dp[i]=dp[q[l]];
            else dp[i]=dp[q[l]]+1;
            while(l<=r&&(dp[q[r]]>dp[i]||(dp[q[r]]==dp[i]&&a[q[r]]<=a[i])))r--;
            q[++r]=i;
        }
        cout<<dp[n]<<endl;
    }
}

luogu P3572 [POI2014]PTA-Little Bird |单调队列

原文：https://www.cnblogs.com/naruto-mzx/p/11855720.html