P3572题解

DDream白日梦 / 2023-08-16 / 原文

P3572题解

题面翻译

有 \(n\) 棵树排成一排，第 \(i\) 棵树的高度是 \(d_i\)。

有 \(q\) 只鸟要从第 \(1\) 棵树到第 \(n\) 棵树。

当第 \(i\) 只鸟在第 \(j\) 棵树时，它可以飞到第 \(j+1, j+2, \cdots, j+k_i\) 棵树。

如果一只鸟飞到一颗高度大于等于当前树的树，那么它的劳累值会增加 \(1\)，否则不会。

由于这些鸟已经体力不支，所以它们想要最小化劳累值。

题解

考虑一种复杂度为 \(O(n^2q)\) 的朴素做法，显然不可过。

观察题目，发现转移的区间是近似于滑动窗口的。考虑单调队列优化。

对于单调队列有一句经典的话： 如果一个选手比你小，还比你强，你就可以退役了 。我们通常有一个误区，那就是队列内的点都是会产生贡献的转移点，但其实不是。单调队列内的点是有优劣之分的，我们之所以保存其他点，是因为最优的点会退役，而其他点会在之后成为最优点。从某种程度上来说，这与但单调栈是类似的，这也是保证复杂度的关键。

回到本题，我们在队列中留下 \(dp\) 与 \(a\) 相对优的值，线性 \(dp\) 即可。

代码:

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+100;
int n,a[N],q,k,dp[N];
list<int>z;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	cin>>q;
	while(q--)
	{
		cin>>k;
		z.clear();
		z.push_back(1);
		for(int i=2;i<=n;i++)
		{
			if(z.size()!=0&&i-z.front()>k)
			z.pop_front();
			dp[i]=dp[z.front()]+(a[z.front()]<=a[i]);
			while(z.size()!=0&&(dp[z.back()]>dp[i]||(dp[z.back()]==dp[i]&&a[z.back()]<a[i])))
			z.pop_back();
			z.push_back(i);
		}
		cout<<dp[n]<<endl;
	}
	return 0; 
}