本蒟蒻学习单调队列DP时，由于太弱做不来难题，所以找到了这道，学什么都应该循序渐进。

每一个询问单独考虑，显然点i可能由i-K，i-K+1……i-1递推得到，方程为 $f[i] = min(f[j] + (a[j]\le a[i])),(max(1,i-K)\le j < i)$，可以得到50分。

#include <bits/stdc++.h>
#define MAX (1000000 + 7)
using namespace std;

int N, K, T, a[MAX], f[MAX];

int main()
{
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
		scanf("%d", a + i);
	
	scanf("%d", &T); while (T--)
	{
		scanf("%d", &K);
		for (int i = 2; i <= N; i++)
		{
			f[i] = 1e9;
			for (int j = max(1, i-K); j < i; j++)
				f[i] = min(f[i], f[j] + (a[i] >= a[j]));
		}printf("%d\n", f[N]);
	}
}

我们发现每个点只从前K个点中选取答案，并且选取的是f的最小值（f一样则显然取a最大更好），每一次i往后移的左右边界变化很小。

这个模型正是单调队列裸题P1440 求m区间内的最小值和P1886 滑动窗口的模型。

我们可以用单调队列来维护前K个数里f[i]的最小值（f[i]一样则取a[i]最大值）。实时将超过长度限制（小于i-K）和无用（比i靠左并且f值还比i大）元素弹出并将i入队即可。

需要注意的是，f[i]不能用来更新自己，所以要先更新f[i],再弹出无用元素，最后将i入队。

#include <bits/stdc++.h>
#define MAX (1000000 + 7)
using namespace std;

int N, K, T, a[MAX], f[MAX];
int L, R, Q[MAX];

int main()
{
	scanf("%d", &N);
	for (int i = 1; i <= N; i++)
		scanf("%d", a + i);
	
	scanf("%d", &T); while (T--)
	{
		scanf("%d", &K), Q[L = R = 1] = 1;
		for (int i = 2; i <= N; i++)
		{
			while (L<=R && i-K>Q[L]) L++;
			f[i] = f[Q[L]] + (a[Q[L]] <= a[i]);
			while (L<=R && (f[Q[R]]>f[i] || (f[Q[R]]==f[i] && a[Q[R]]<=a[i]))) R--;
			Q[++R] = i;
		}printf("%d\n", f[N]);
	}
}

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int dp[N],n,k,a[N];
struct node{int v,id,h;};
void solve()
{
	cin>>k;memset(dp,0,sizeof(dp));
	deque<node>q;
	q.push_back({0,1,a[1]});
	for(int i=2;i<=n;i++)
	{
		while(!q.empty()&&i-q.front().id>k)q.pop_front();
		dp[i]=q.front().v+(q.front().h<=a[i]);
		while(!q.empty()&&q.back().v+(q.back().h<a[i])>dp[i])q.pop_back();
		q.push_back({dp[i],i,a[i]});
	}
	cout<<dp[n]<<'\n';
}
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	int q;cin>>q;
	while(q--)solve();
	return 0;
}