Little Bird（单调队列优化的DP）

ruoye123456 / 2024-08-23 / 原文

题目描述
有一排$n$棵树，第$i$棵树的高度是$d_i$。有一只鸟要从第$1$棵树飞到第$n$棵树。

如果鸟降落在第$i$棵树，那么它下一步可以降落到第$i+1,i+2,\dots,i+k$棵树之中的一棵。

如果鸟降落到一棵不矮于当前树的树，那么它的劳累值会$+1$，否则不会。

求劳累值的最小值。
输入
第一行一个正整数$T(1\leq T\leq 2)$，表示测试数据的数量。

每组数据第一行一个正整数$n(2\leq n\leq 10^6)$，表示树的数量。

第二行$n$个正整数$d_1,d_2,\dots,d_n(1\leq d_i\leq 10^9)$，表示每棵树的高度。

第三行一个正整数$q(1\leq q\leq 25)$，表示询问的数量。

接下来$q$行，每行一个正整数$k(1\leq k\leq n-1)$，表示一个询问。
输出
每组数据输出$q$行，每行一个整数，即在给定的$k$下劳累值的最小值。
样例输入 Copy
1
9
4 6 3 6 3 7 2 6 5
2
2
5
样例输出 Copy
2
1

check函数若从lambda改为bool会超时，加inline可以过

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int N = 1e6+10;
int q[N],d[N],f[N];
void solve()
{
	//先考虑二维dp,用f[i]表示从1飞到i的劳累值最小值
	//f[i] = min(f[j]+(d[j]<=d[i])) i-k<=j<=i-1
	//考虑对于j<k
	//若f[j]>f[k]的,k一定更优
	//若f[j]<f[k],则j更优
	//若f[j]==f[k],则d更高的优
	int n;
	cin>>n;
	for(int i=1;i<=n;++i) cin>>d[i];
	int Q;
	cin>>Q;
	while(Q--)
	{
		int k;
		cin>>k;
		//for(int i=1;i<=n;++i) cout<<d[i]<<" \n"[i==n];
		int h = 1,t = 0;
		auto check = [&](int j,int k)->bool
		{
			if(f[j] > f[k]) return true;
			else if(f[j] < f[k]) return false;
			else return d[k] >= d[j];
		};
		for(int i=1;i<=n;++i) 
		{	
			if(i >= k+1) while(h<=t&&q[h]<i-k) h++;
			if(i==1) f[i] = 0;
			else if(h<=t) 
			{
				//注意取的是队首
				f[i] = f[q[h]] + (d[q[h]]<=d[i]);
			} 
			//在本题中应该先计算f[i]后更新单调队列
			while(h<=t&&check(q[t],i)) t--;
			q[++t] = i;
		}
		cout<<f[n]<<'\n';
	}
	
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	cin>>T;
	while(T--)
	{
		solve();
	}
}