题意

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

分析

不难得出转移方程:
f i = m i n ( f j + [ a i a j ] ) <mtext>      </mtext> ( i k j i 1 ) f_i = min(f_j + [a_i \geq a_j])~~~~(i-k\leq j\leq i-1) fi=min(fj+[aiaj])    (ikji1)
然后我们考虑在范围内的 f j f_j fj
如果 f j + 1 < f j f_{j+1} < f_j fj+1<fj,那么显然 f j + 1 f_{j+1} fj+1 更优,因为又小又在后面
如果 f j + 1 = f j f_{j+1}=f_j fj+1=fj a j + 1 > = a j a_{j+1} >= a_j aj+1>=aj,那么还是 f j + 1 f_{j+1} fj+1 更优,可以取而代之。
这样其实是按双关键字排序的过程。
这样,我们就可以维护一个 f 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;
}