Little Bird

【题目描述】

现有N(2 <= N <= 10⁶)棵树，第i棵树的高度为D_i(1 <= D_i <= 10⁹)。

雏鸟想要从第1棵树跳到第N棵树，如果雏鸟在第i棵树，那么它可以跳到第i+1、i+2、······、i+K(1 <= K < N)棵树。如果雏鸟跳到一棵不矮于当前树的树，那么它的劳累值会+1，否则不会。

询问雏鸟所能达成的最小劳累值是多少。

【输入描述】

第一行输入一个整数N，表示树的个数；

第二行输入N个整数，分别表示第i棵树的高度D_i；

第三行输入一个整数Q(1 <= Q <= 25)，表示K的个数；

接下来Q行，每行输入一个整数K。

【输出描述】

输出Q行，每行包含一个整数，表示雏鸟在此K情况下所能达到的最小劳累值。

【输入样例】

9

4 6 3 6 3 7 2 6 5

2

2

5

【输出样例】

2

1

普通的O(nmk)DP解法：

源代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int m,n,i[1000001],f[1000001];
void Solve(int k)
{
    f[1]=0;
    for (int a=1;a<=n;a++)
      for (int b=a-1;b>=a-k&&b>0;b--)
        if (i[a]<i[b])
          f[a]=min(f[a],f[b]);
        else
          f[a]=min(f[a],f[b]+1);
    printf("%d
",f[n]);
}
int main()
{
    scanf("%d",&n);
    for (int a=1;a<=n;a++)
      scanf("%d",&i[a]);
    scanf("%d",&m);
    for (int a=1;a<=m;a++)
    {
        int k;
        scanf("%d",&k);
        memset(f,0x3f,sizeof(f));
        Solve(k);
    }
    return 0;
}

单调队列优化的O(nm)解法：

源代码：

#include<cstdio>
#include<algorithm>
using namespace std;
int m,n,k,i[1000001],f[1000001],Q[1000001],head,tail;
int main() //竟然可以优化到O(n)，看来优先队列挺值得学习的。
{
    scanf("%d",&n);
    for (int a=1;a<=n;a++)
      scanf("%d",&i[a]);
    scanf("%d",&m);
    while (m--)
    {
        head=1; //队头。
        tail=0; //队尾。
        scanf("%d",&k);
        f[1]=0; //开头并不需要花费体力。
        Q[++tail]=1; //Q[]中存储的是树的编号。
        for(int a=2;a<=n;a++) //DP过程。
        {
            if (a-Q[head]>k) //距离＞K，故已过期。
              head++;
            if (i[a]>=i[Q[head]]) //状态转移方程。
              f[a]=f[Q[head]]+1;
            else
              f[a]=f[Q[head]];
            while (head<=tail&&f[a]<=f[Q[tail]]) //跳到tail树的代价＞a树的代价时。
            {
                if (f[a]==f[Q[tail]]&&i[a]<i[Q[tail]]) //代价相等取其高。
                  break;
                tail--; //跳出没有用的节点。
            }
            Q[++tail]=a; //处理完后就可以在合适的地方入队了。
        }
        printf("%d
",f[n]);
    }
    return 0;
}