洛谷p3572 [POI2014] PTA-Little Bird（单调队列优化dp

题意

有 $n$n 个点， 每次从高的点到低的点不消耗体力，从低的点到高的点消耗 $1$1 点体力，问从 $1$1 到 $n$n 消耗的最少体力。

分析

不难得出转移方程：
$f_i=min(f_j+[a_i\ge a_j\left]\right)(i-k\le j\le i-1)$fi​=min(fj​+[ai​≥aj​])    (i−k≤j≤i−1)
然后我们考虑在范围内的 $f_j$fj​
如果 fj+1​<fj​，那么显然 $f_{j+1}$fj+1​ 更优，因为又小又在后面
如果 $f_{j+1}=f_j$fj+1​=fj​ 且 $a_{j+1}>=a_j$aj+1​>=aj​，那么还是 $f_{j+1}$fj+1​ 更优，可以取而代之。
这样其实是按双关键字排序的过程。
这样，我们就可以维护一个 $f$f 的单调队列，满足队列中的元素按双关键字排序。这道题就解决了。

代码如下

#include <bits/stdc++.h>
#define N 1000007
using namespace std;
int f[N], a[N], x, y, q[N];
int main(){
	int i, j, n, m, k, qu;
	scanf("%d", &n);
	for(i = 1; i <= n; i++) scanf("%d", &a[i]);
	scanf("%d", &qu);
	while(qu--){
		scanf("%d", &k);
		memset(f, 1, sizeof(f));
		f[1] = 0; q[x = y = 1] = 1;
		for(i = 2; i <= n; i++){
			if(x <= y && i - q[x] > k) x++;
			while(x < y){
				if(f[q[y]] < f[q[y - 1]] || (f[q[y]] == f[q[y - 1]] &&  a[q[y]] >= a[q[y - 1]])) q[y - 1] = q[y], y--;
				else break;
			}
			f[i] = f[q[x]] + (a[i] >= a[q[x]]);
			q[++y] = i;
		}
		printf("%d\n", f[n]);
	}
	return 0;
}