bzoj3831[Poi2014] Little Bird（单队）

Description
有一排n棵树，第i棵树的高度是Di。
MHY要从第一棵树到第n棵树去找他的妹子玩。
如果MHY在第i棵树，那么他可以跳到第i+1,i+2,…,i+k棵树。
如果MHY跳到一棵不矮于当前树的树，那么他的劳累值会+1，否则不会。
为了有体力和妹子玩，MHY要最小化劳累值。

Input
第一行是一个整数n，表示有n棵树。(n<=1 000 000)
第二行有n个数，第i个数表示第i棵树的高度。
第三行有一个整数Q，表示有Q个询问(Q<=25)
接下来有Q行，第j行有一个整数kj。表示每一个询问的k。

Output
对于每个询问，输出最小劳累值。

Sample Input
9
4 6 3 6 3 7 2 6 5
2
2
5

Sample Output
2
1

分析：
首先，这个题面很值得吐槽。。。
先来一个很zz的转移
f[i]表示到第i棵树的最小疲劳值
f[i]=min{f[j]+[a[i]>=a[j]]} (i-k <= j < i)
时间复杂度O(Qnk)，显然T

那么我们考虑

单调队列优化

单调队列里储存的f值从小到大，
每次更新f[i]时，就从队首的状态转移
f[i]=f[q[tou]]+(h[q[tou]]<=h[i] ? 1:0)

维护队首很简单：编号

这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>

using namespace std;

const int N=1000001;
int n,k;
int h[N],f[N];
int q[N],tou,wei;

void doit()
{
    tou=0;
    wei=1;
    q[wei]=1;
    memset(f,0,sizeof(f));
    for (int i=2;i<=n;i++)
    {  //单调队列值是从小到大 
        while (tou<wei&&q[tou]<i-k) tou++;  //队首出列 
        f[i]=f[q[tou]];
        if (h[q[tou]]<=h[i]) f[i]++;
        while (tou<wei&&f[q[wei]]>f[i])  wei--;  //当前状态优 
        while (tou<wei&&f[i]==f[q[wei]]&&h[q[wei]]=<h[i]) wei--;  //一样的情况下，高的肯定好啊  
        q[++wei]=i; 
    }
    printf("%d
",f[n]);
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&h[i]);
    int Q;
    scanf("%d",&Q);
    while (Q--)
    {
        scanf("%d",&k);
        doit();
    }
    return 0;
}