标签：huge le 队列 算法 DP 随笔 优化 单调

单调队列优化DP

单调队列模板：

int head = 1,tail = 0;
	for (int i = 1;i <= n;i++)
	{
		while (head <= tail && head 不满足条件) head++;//踢出队列
		f[i] = f[q[head]] + ...;
		while (head <= tail && tail 与 i 不满足单调性) tail--;
		q[++tail] = i;
	}

优化思路则是对于类似于这样的 dp 式：

\[\huge {f_i = \max _{i-M <= j <= i-1}\{ f_j + w \}} \]

在其中求区间最值时，因为其上下限均单调变化，因此可以用单调队列将转移优化到 \(O(1)\) 。

单调队列优化多重背包

单调队列优化多重背包

思路

首先我们列出 dp 式：

\[\huge{f_j = \max_{1 \le cnt \le s _ i} \{ f _ j-cnt*v_i + cnt * w_i \}} \]

我们考虑将第二维 \(V\) 按照除以 \(v_i\) 的余数分组。

对于每个余数 \(u \in [0,v_i-1]\)，倒序循环 \(p = (V-u)/v_i\)。
因此可以写出新的状态转移方程：

\[\huge{f_{u + p * v_i} = \max _{p-s_i \le k \le p-1} \{ f_{u + k * v _ i} + (p-k)*w _ i \}} \]

标签：huge,le,队列,算法,DP,随笔,优化,单调
From： https://www.cnblogs.com/codwarm/p/18314697