题意

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

数据范围：$2 \le n \le 1000000$

题解

用$f[i]$表示前$i$个的步数，易得状态转移方程

$$ f[i]=\min_{j=i-k}^{i-1}\left\{ \begin{aligned} &f[j] &a[j] > a[i] \\ &f[j]+1 &a[j] \le a[i] \end{aligned} \right. $$

但是这样是$O(n^2)$的，显然无法通过此题
观察到单调性，考虑使用单调队列优化
单调性考虑两个方面：

• $f[i]$单调递增
  显然$f[i]$越小，对更新答案越有帮助
• $a[i]$单调不减
  在$f[i]$相同时，更大的$a[i]$更有可能不会$+1$

由于$f[i]$不能用来更新自己，实现时需先弹出过期元素，更新自己后再入队

代码：

#include<iostream>
#include<cstdio>
using namespace std;
const int N=1000000+10;
int n,q,k;
int a[N];
int hd,tl;
int dp[N],mq[N];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    scanf("%d",&q);
    for(;q--;){
        scanf("%d",&k);
        hd=1,tl=0;
        mq[++tl]=1;
        for(int i=2;i<=n;i++){
            for(;hd<=tl && mq[hd]<i-k;hd++);
            dp[i]=dp[mq[hd]]+(a[mq[hd]]<=a[i]);
            for(;hd<=tl && (dp[mq[tl]]>dp[i] || (dp[mq[tl]]==dp[i] && a[mq[tl]]<=a[i]));tl--);
            mq[++tl]=i;
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}