题面：

题解：

N<=1e6 Q<=25

F[i]表示到达第i棵树时需要消耗的最小体力值

F[i]=min(F[i],F[j]+(D[j]>=D[i])) (j>=i-K)

使用单调队列维护

越小的越优，在写单调队列时，让F值最小的数越前

因为F[i]-F[j]最多等于1

然后如果F值相同，则D越大的越优，因为D越大，后面不用+1的概率越大

大概就是这样

代码：

1 #include
     
       2 #include
      
        3 #define min(a,b) ((a)<(b)?(a):(b)) 4 #define max(a,b) ((a)>(b)?(a):(b)) 5 using namespace std; 6 int rd(){ 7     int x=0; char c=getchar(); 8     while(c<'0'||c>'9') c=getchar(); 9     while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();}10     return x;11 }12 const int maxn=1e6+5,maxq=30,inf=1<<30;13 int N,D[maxn],F[maxn],Q,K,f1,f2;14 int que[maxn];15 int main(){16     N=rd();17     for(int i=1;i<=N;i++) D[i]=rd();18     Q=rd();19     while(Q--){20         f1=1;f2=0;21         que[++f2]=1;22         K=rd();23         for(int i=2;i<=N;i++){24             while(f1<=f2 && que[f1]
       
        D[que[f2]]) f2--;28             que[++f2]=i;29         }30         printf("%d\n",F[N]);31     }32     return 0;33 }
       
      
     

---

By:AlenaNuna