BZOJ3831:[Poi2014]Little Bird dp+单调队列

思路:

一开始是用的线段树优化dp,具体的就不说了.

我一开始觉得有的需要+1,有的不需要加,单调队列没办法做.

不过有一条性质,就是如果两条决策,其中一个的步数已经比另一个决策少,那么我们选择这个决策是一定不劣于另一个决策的.

否则若步数相同,我们当然选择保留高度较高的那个决策.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

namespace Fio{
    inline int getc(){
        static const int L=1<<15;static char buf[L],*S=buf,*T=buf;
        if(S==T){T=(S=buf)+fread(buf,1,L,stdin);if(S==T)return EOF;}
        return*S++;
    }
    template<typename T>inline void Get(T&x){
        int c;while(!isdigit(c=getc())&&c!='-');bool sig=c=='-';
        x=sig?0:c-'0';while(isdigit(c=getc()))x=(x<<1)+(x<<3)+c-'0';
        if(sig)x=-x;
    }
}
#define N 1000010
int h[N];
int q[N],fr,ta,f[N];
int main(){
	int n;Fio::Get(n);register int i,j;for(i=1;i<=n;++i)Fio::Get(h[i]);
	int Q;Fio::Get(Q);int lim;
	while(Q--){
		 Fio::Get(lim);
		 fr=ta=0;q[ta++]=1;f[1]=0;
		 for(i=2;i<=n;++i){
		 	while(fr^ta&&i>q[fr]+lim)++fr;f[i]=f[q[fr]]+(h[q[fr]]<=h[i]);
		 	while(fr^ta&&((f[i]<f[q[ta-1]])||(f[i]==f[q[ta-1]]&&h[i]>h[q[ta-1]])))--ta;
		 	q[ta++]=i;
		 }
		 printf("%d\n",f[n]);
	}return 0;
}