BZOJ_3831_[Poi2014]Little Bird_单调队列优化DP

Description

有一排n棵树，第i棵树的高度是Di。

MHY要从第一棵树到第n棵树去找他的妹子玩。

如果MHY在第i棵树，那么他可以跳到第i+1,i+2,...,i+k棵树。

如果MHY跳到一棵不矮于当前树的树，那么他的劳累值会+1，否则不会。

为了有体力和妹子玩，MHY要最小化劳累值。

Input

There is a single integer N(2<=N<=1 000 000) in the first line of the standard input: the number of trees in the Byteotian Line Forest. The second line of input holds integers D1,D2…Dn(1<=Di<=10^9) separated by single spaces: Di is the height of the i-th tree.

The third line of the input holds a single integer Q(1<=Q<=25): the number of birds whose flights need to be planned. The following Q lines describe these birds: in the i-th of these lines, there is an integer Ki(1<=Ki<=N-1) specifying the i-th bird's stamina. In other words, the maximum number of trees that the i-th bird can pass before it has to rest is Ki-1.

Output

Your program should print exactly Q lines to the standard output. In the I-th line, it should specify the minimum number of tiresome flight legs of the i-th bird.

Sample Input

9
4 6 3 6 3 7 2 6 5
2
2
5

Sample Output

2
1

首先有DP方程F[i]=min(F[j]+(d[i]>=d[j])) (1<=i-j<=k)

可以发现作为决策点，F值小的更优(因为每次最多只加1)，F值相同的高的更优。

于是可以用单调队列优化DP过程。

比较决策点谁更优时先比较F,再比较高度。

代码：

#include <stdio.h>

#include <string.h>

#include <algorithm>

using namespace std;

#define N 1000500

int f[N],d[N],n,m,Q[N],l,r;

bool check(int j,int k) {

    if(f[j]==f[k]) return d[k]>d[j];

    return f[k]<f[j];

}

int main() {

    scanf("%d",&n);

    int i,k;

    for(i=1;i<=n;i++) {

        scanf("%d",&d[i]);

    }

    scanf("%d",&m);

    while(m--) {

        scanf("%d",&k);

        l=r=0;

        f[1]=0;Q[r++]=1;

        for(i=2;i<=n;i++) {

            while(l<r&&i-Q[l]>k) l++;

            f[i]=f[Q[l]]+(d[i]>=d[Q[l]]);

            while(l<r&&check(Q[r-1],i)) r--;

            Q[r++]=i;

        }

        printf("%d\n",f[n]);

    }

}

秒客网