luogu P3572 [POI2014]PTA-Little Bird

题目描述

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

---

单调队列优化动态规划

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=1e6+10;

#define int long long

int a[N],dp[N],q[N],l,r=1;

int n,m,k;

inline void in(){

    cin>>n;

    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);

    cin>>m;

}

signed main(){

	in();

    while(m--){

        scanf("%lld",&k);

		l=r=1,q[r]=1;

        for(int i=2;i<=n;i++){

        	while(l<=r&&i-q[l]>k)l++;

			if(a[q[l]]>a[i])dp[i]=dp[q[l]];

        	else dp[i]=dp[q[l]]+1;

        	while(l<=r&&(dp[q[r]]>dp[i]||(dp[q[r]]==dp[i]&&a[q[r]]<=a[i])))r--;

        	q[++r]=i;

		}

		cout<<dp[n]<<endl;

	}

}