单调队列优化DP

单调队列优化DP

​ \%Sunward\text{_}z，神仙在线教会蒟蒻单调队列优化 $dp$。

思想

​ 考虑到做动规的题目时会经常遇到形如这样的转移方程：

$dp_{i,j}=\max(dp_{i-1,j}+a_j)_{(l\leq j\leq r)}+b_i$

​ 朴素的做法单次转移时间复杂度为 $O(n)$，放进所有的情况里就基本无法拿分。

​ 那么这时考虑到对于 $\max$ 中的东西可以放进一个单调队列中，对于所有的情况只需要遍历一次数组，而单次转移状态的均摊复杂度则为 $O(1)$，非常容易理解，代码也简单。

例子 洛谷-CF372C Watching Fireworks is Fun

​ 读题后可以显然得到转移方程：

${dp_{i,j} }_{(1\leq i\leq m,1\leq j\leq n)}=\max(dp_{i-1,j+k})_{(-d\cdot t_i\leq k\leq d\cdot t_i)}+b_i-|a_i-j|$

​ 朴素的做法时间复杂度为 $O(n\cdot m^2)$，而考虑对于 $\max$ 内的东西维护一个单调队列，那么时间复杂度为 $O(n\cdot m)$。

​ 细节注意，需要来回遍历两次，单次操作维护两次单调队列。放一份核心代码：

rep(i, 2, m)
{
	last = cur;
	cur = !cur;
	memset(dp[cur], 0x3f3f3f, sizeof(dp[cur]));
	int l(1), r(0), time = t[i] - t[i - 1];
	rep(j, 1, n)
	{
		while(l <= r && q[l] < j - time * d) ++l;
		while(l <= r && dp[last][q[r]] > dp[last][j]) --r;
		q[++r] = j;
		dp[cur][j] = min(dp[cur][j], dp[last][q[l]] + abs(a[i] - j));
	}
	l = 1, r = 0;
	for(register int j = n; j >= 1; -- j)
	{
		while(l <= r && q[l] > j + time * d) ++ l;
		while(l <= r && dp[last][q[r]] > dp[last][j]) --r;
		q[++r] = j;
		dp[cur][j] = min(dp[cur][j], dp[last][q[l]] + abs(a[i] - j));
	}
}

​ 这个代码是神仙 Sunward_z 的~~（觉得自己的代码这题写得比较丑就没放上去了）~~。