3831: [Poi2014]Little Bird

Description

Input

Output

首先这是一道权限题（权限号？XMCXMC!)

显然的算法是O(nk)，f[i] = min(min(f[j]+1)(D[i]>=D[j]),min(f[j])(D[i]<D[j]))(i-j<=k)

不过我们可以发现，当i<j且f[i]>f[j],那么i就不可能被用于转移。

同理若i<j且f[i]=f[j],a[i]<=a[j]，那么i也不会被用于转移。

所以可以用单调队列优化DP。

核心代码如下：

            if (i-q[l] > k) l++;           
            f[i] = a[i]>=a[q[l]]?f[q[l]]+1:f[q[l]];
            for (;r&&(f[i]<f[q[r]]||(f[i] == f[q[r]]&&a[i]>a[q[r]]));r--);
            q[++r] = i;

我的DP还是太弱辣（蒟蒻就该多做题！)，还是要多向黈力学习！