POI2014 PTA-Little Bird

题目链接

题解

要用单调队列这一点比较明显，DP也可以看得出来。
所以就是单调队列+DP。
保证单调队列里的元素相同体力消耗下靠近队首的高度尽量高即可，
相当于在维护队列体力消耗值从队首到队尾递增的基础上对高度进行递减的维护。
时间复杂度是$O(Nq)$。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cctype>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f=1,x=0;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return f*x; 
}
int n,a[1000005],m,d,que[1000005],f,r,dp[1000005];
void init(){
    n=read();
    for(int i=1;i<=n;i++)a[i]=read();
}
void solve(){
    m=read();
    while(m--){
        d=read();
        f=r=0;
        dp[1]=0,que[r++]=1;
        for(int i=2;i<=n;i++){
            while(r-f&&i-que[f]>d)f++;
            dp[i]=dp[que[f]]+(a[que[f]]<=a[i]);
            while(r-f&&(dp[que[r-1]]>dp[i]||(dp[que[r-1]]==dp[i]&&a[que[r-1]]<a[i])))
                r--;
            que[r++]=i;
        }
        printf("%d\n",dp[n]);
    }
}
int main(){
    init();
    solve();
    return 0;
}