题意
有 (n) 棵树，第 (i) 棵树的高度是 (d_i)。
( exttt{HLY}) 要去第 (n) 棵树。
如果 ( exttt{HLY}) 在第 (i) 棵树，那么他可以跳到第 (i+1,i+2,cdots,i+k) 棵树。
如果她跳到一棵不矮于当前树的树，那么他的劳累值会 (+1)；否则不会。
求 ( exttt{HYL}) 到达第 (n) 棵树的最小劳累值。
考试的时候想到了可以用单调队列来优化，结果却 yy 出了一种错误的想法，维护最大值和次大值。
结果，最后只能交了 (n^2) 的暴力滚粗。
首先， (n^2) 的暴力dp，肯定都比较容易想到。
(f[i] = min(f[i], f[j] + (h[i] >= h[j]) ) 其中 j in {1,i-k})
这个就可以联想到单调队列优化，因为是求 (i-k,i) 的区间最小值。
但这个高度就处理起来很麻烦。
我们考虑什么时候是不优的。
- (f[q[tail]] < f[i]) ，也就是说 (f[q[tail]] >= f[i] + 1) ,我们直接可以把 (q[tail]) 出队。
- 就算 (f[q[tail] + 1) 也不会比 (f[i]) 更优。
- (f[q[tail]] = f[i]) 这时候就要仔细想想了，如果 (f) 数组的值相同的话，我们要尽可能的让高度大的留下来，因为这样后面转移时可以承接更多的树，也是就会
- 使加一的次数变小很多。
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n,t,k,head,tail,h[1000010],f[1000010],q[1000010];
inline int read()
{
int s = 0,w = 1; char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
while(ch >= '0' && ch <= '9'){s =s * 10+ch - '0'; ch = getchar();}
return s * w;
}
int main()
{
// freopen("t4.in","r",stdin);
// freopen("t4.out","w",stdout);
n = read();
for(int i = 1; i <= n; i++) h[i] = read();
t = read();
while(t--)
{
k = read();
memset(f,0x3f,sizeof(f));
head = 1,tail = 0;
f[1] = 0; q[++tail] = 1;//先把一号点入队
for(int i = 2; i <= n; i++)
{
while(head <= tail && q[head] < i-k) head++;//把过期的元素弹出
if(h[q[head]] <= h[i]) f[i] = f[q[head]] + 1;//先更新在把这个点入队
else f[i] = f[q[head]];
while(head <= tail && (f[q[tail]] > f[i] || (f[q[tail]] == f[i] && h[q[tail]] <= h[i]))) tail--;//特判一下f值相同的情况
q[++tail] = i;
}
printf("%d
",f[n]);
}
fclose(stdin); fclose(stdout);
return 0;
}