第一次写单调队列优化DP的题解QWQ

一、题面

点这里

二、分析

如果不看数据范围，这道题显然是一道简单的线性DP。设 $f[i]$ 表示跳到第 $i$ 棵树所需要的最小劳累值（根据题目意思只能这么设状态），显然 $f[i]=min{f[j]+(d[j]<=d[i])}(i-k \le j < i)$（可能从第 $j$ 棵树跳过来），初值 $f[1]=0$ 。

然而

$2 \le n \le 10^6$ ！！！

所以只能采取线性的做法。

根据状态转移方程，$f[i]$ 只可能从一个固定范围转移过来（$i-k \le j <i$），而且求的是范围里的最小值。在数据规模很大的情况下，马上可以想到单调队列（不懂的自行BFS）。因为 $f[j]$ 确定，$d[j]$ 与 $d[i]$ 的关系就确定了。所以我们用单调队列存储 $i-k \sim i-1$ 中 $f$ 的最优值。现在的问题是：怎么确定最优值。

假设现在即将进队的元素是 $f[x]$ ，当前队尾元素是 $f[y]$ 。可以分情况讨论：

• $f[x]==f[y]$ ：

  劳累值相同，此时只需要比较树的高度。因为树的高度越高，后面的树比这棵树矮的可能性就越大，所以选更高的。

• $f[x]>f[y]$ ：

  $y$ 一定比 $x$ 优，至少不会差。因为即使从 $y$ 到当前树，劳累值需要加 $1$ ，而从 $x$ 到当前树，劳累值不改变。那么 $f[x]>=f[y]+1$ （都是整数），$y$ 不会比 $x$ 差。此时选 $y$ 。反之同理。

单调队列可以用STL中的deque实现，具体细节见代码：

三、代码

#include <cstdio>
#include <deque>
inline int read(){
	int x=0,w=0;char c=getchar();
	for(;c<'0'||c>'9';w^=c=='-',c=getchar());
	for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=getchar());
	return w?-x:x;
}//本题最好加快读
int n,d[1000003],Q,k,f[1000003];
std::deque<int> q;
int main(){
	n=read();
	for(int i=1;i<=n;i++) d[i]=read();
	Q=read();
	while(Q--){
		k=read();
		q.clear();//每次一定要先清空
		q.push_back(1),f[1]=0;
		for(int i=2;i<=n;i++){
			while(!q.empty()&&q.front()<i-k)
                q.pop_front();//只维护i-k到i-1的f的值，如果队头超过这个范围就要出队
			f[i]=f[q.front()]+(d[q.front()]<=d[i]);//这句话要先做，因为下面会用到
			while(!q.empty()&&(f[q.back()]>f[i]||f[q.back()]==f[i]&&d[q.back()]<d[i])
                q.pop_back();//这里从队尾和i中选最优值
			q.push_back(i);
		}
		printf("%d\n",f[n]);
	}
	return 0;
}

但是出题人居然丧心病狂地卡了STL，所以需要用数组模拟队列，改一下就好了。