对于这道题可以很容易写出状态转移方程。但直接转移会超时,所以需要单调队列优化。这里的单调队列采取左闭右开写法,容易理解。
怎么做呢?常规取出队头决策就不多说了。怎么判断当前决策是否更优呢?当状态较优秀且树高比较高,就可以考虑去掉尾巴。
代码:
#include <bits/stdc++.h> #define rep(i,a,b) for(int i=(a);i<=(b);++i) #define fo(i,a,b) for(int i=(a);i<(b);++i) using namespace std; const int N=1e6+5; int d[N],n; int f[N],q[N]; void solve(int k){ memset(f,0x3f,sizeof f); int hh=0,tt=0; f[1]=0; q[tt++]=1; for(int i=2;i<=n;i++){ while(hh<tt&&i-q[hh]>k) hh++; if(hh<tt) { if(d[q[hh]]>d[i]) f[i]=f[q[hh]]; else f[i]=f[q[hh]]+1; } while(hh<tt&& ( f[i]<f[q[tt-1]]|| (f[i]==f[q[tt-1]]&&d[i]>=d[q[tt-1]]) )) tt--; q[tt++]=i; } cout<<f[n]<<'\n'; } int main(){ cin>>n; rep(i,1,n) cin>>d[i]; int Q; cin>>Q; rep(kase,1,Q){ int k; cin>>k; solve(k); } }