题解 PTA-Little Bird

Description

有一个鸟，从1开始，跳到比当前矮的树不消耗体力，否则消耗一点体力，每次询问有一个步伐限制，求每次最少耗费多少体力

其实是可以用下标做单调队列的~

注意到：

$dp[i]=\min_{i-k<= j<i}\{dp[j]+[h_j<=h_i]\}$

这两个都和j有关，就可以打包成pair扔进单调队列。

或者直接存下标。

这个单调队列的单调性不仅由dp[i]决定，还有h决定。

显然，当dp值相同的时候，我们站的高度应该越高越好

所以入队时多判断一下就行。

#include <bits/stdc++.h>
using namespace std;
const int N=1000009;

int n,q,k,ans;
int h[N],dp[N];
deque<int> Q;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&h[i]);
	scanf("%d",&q);
	while(q--)
	{
		Q.clear();
		scanf("%d",&k);
        //Q.push_back(1);
		for(int i=1;i<=n;i++)
		{
			while(!Q.empty()&&i-Q.front()>k) Q.pop_front();
			if(!Q.empty()) dp[i]=dp[Q.front()]+(h[Q.front()]<=h[i]);
			while(!Q.empty()&&(dp[i]<dp[Q.back()]||(dp[i]==dp[Q.back()]&&h[i]>=h[Q.back()]))) Q.pop_back();
			Q.push_back(i);
		}
		printf("%d\n",dp[n]);
	}
	return 0;
}