题目简介见https://www.luogu.org/problemnew/show/P3572
dp 方程应该很好写 （a 数组 为 树的高度）
j + k >= i 且 j < i
a[j] > a[i] 时 f[i] = min (f[i] , f[j]) ;
a[j] <= a[i] 时 f[i] = min (f[i] , f[j] +1 );
但是 复杂度 N^2*q 老爷机 受不了；
只能优化喽 ；
推断1 ： 如果有 j > k 且 f[j] < f[k] 那么 j 永远比 k 优；
此时可以用单调队列； 执行推断1
但是 我们还要考虑树的高度；
推断2 ：当单调队列中 j > k 且 f[j] == f[k] 且 a[j] > a[k] 那么j 比 k 更优秀 ；
终上所述 我们维护f非严格递增 ， 当f相同时 ， 维护a递减；
代码：
#include<cstdio> #include<cmath> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<stack> #include<cstring> using namespace std; #define M 1000100 #define ll long long int n , m , f[M] , a[M] , maxn , high , k , q[M] , l , r; void solve(){ l = r = 1; q[1] = 1; memset(f , 0x3f , sizeof(f)); f[1] = 0; for (int i = 2 ; i <= n ; ++i){ while (l <= r && q[l] + k < i ) ++l; if (a[q[l]] > a[i]) f[i] = f[q[l]]; else f[i] = f[q[l]] + 1; while (f[i] < f[q[r]] && r >= l) --r; while (f[i] == f[q[r]]){ if (a[i] >= a[q[r]]) --r; else break; } q[++r] = i; } printf ("%d " , f[n] ); } int main(){ freopen("c1.in" , "r" , stdin); // freopen("A.out" , "w" , stdout); scanf("%d" , &n); for (int i = 1 ; i <= n ; ++i) scanf("%d" , a + i); scanf("%d" , &m); while (m--){ scanf("%d" , &k); solve(); } return 0; }