题意
有 n 个点, 每次从高的点到低的点不消耗体力,从低的点到高的点消耗 1 点体力,问从 1 到 n 消耗的最少体力。
分析
不难得出转移方程:
fi=min(fj+[ai≥aj]) (i−k≤j≤i−1)
然后我们考虑在范围内的 fj
如果 fj+1<fj,那么显然 fj+1 更优,因为又小又在后面
如果 fj+1=fj 且 aj+1>=aj,那么还是 fj+1 更优,可以取而代之。
这样其实是按双关键字排序的过程。
这样,我们就可以维护一个 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;
}