洛谷3572 [POI2014]PTA-Little Bird

题意

有 $N$ 个点，从 $1$ 开始跳，跳到高度比当前矮的点免费，否则消耗 $1$ 。有 $M$ 次询问，每次给出最长能跳的距离，求跳到 $N$ 的最小花费。

$N\le 10^6 \ , \ M\le 25$ 。

题解

用 $f[i]$ 表示跳到 $i$ 的最小花费，则

$$f[i]=\min_{i-j\le q} \begin{cases} f[j] \ (H_j > H_i) \\ f[j]+1 \ (H_j\le H_i) \end{cases}$$

那么就把高度关系看成权值，用单调队列即可。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar(); int f=1,x=0;
    while (ch<'0' || ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
    while (ch>='0' && ch<='9') { x=x*10+ch-'0'; ch=getchar(); }
    return f*x;
}

int n,m,mx,h[1000005],q[1000005],f[1000005];

signed main()
{
    n=read();
    for (int i=1;i<=n;i++) h[i]=read();
    m=read();
    while (m--)
    {
        mx=read();
        int l=1,r=1; q[1]=1;
        for (int i=2;i<=n;i++)
        {
            while (l<=r && i-q[l]>mx) l++;
            f[i]=f[q[l]]+(h[i]>=h[q[l]]);
            while (l<=r && f[q[r]]+(h[q[r]]<=h[i])>f[i]) r--;
            q[++r]=i;
        }
        printf("%d\n",f[n]);
    }
    return 0;
}