DP 常见优化技巧

摘要

DP 优化的核心思想：在状态转移时及时排除不可能最优的决策，保持候选集合的有效性和秩序性。

倍增优化

有点复杂，先跳过：【紫色】P1081 [NOIP 2012 提高组] 开车旅行 - 洛谷。

单调队列优化

OI 是一个单调队列，如果有人比你年龄小，还比你强，那么你应该出列了。

单调队列维护可行决策集合基于这一思想：如果：

$j_2$ 比 $j_1$ 总是更容易符合转移条件；

$j_2$ 比 $j_1$ 的收益总是更不差

那么 $j_2$ 总是一个比 $j_1$ 更好的选择，此时 $j_1$ 应该出列。

对于状态转移方程模型： $$ f(i) = \max_{L(i) \le j \le R(i)}\set{f(j) + val(i,j)} $$ 且 $val(i,j)$ 的每一项仅与 $i, j$ 其中一个有关，可以使用单调队列维护可行决策以缩小决策范围。

【蓝色】P10978 Fence - 洛谷状态转移方程如下： $$ f(i,j) = \max\begin{Bmatrix} f(i-1, j) & & \ f(i, j-1) & & \ \max_{j-L_i \le k < j}\set{f(i-1, k) +p_i \times (j-k)} & k < S_i & \ \end{Bmatrix} $$

【紫色】P10977 Cut the Sequence - 洛谷状态转移方程如下： $$ f(i) = \min_{0 \le j < i \land \sum_{k=j+1}^{i} a_k \le M}\set{f(j) + \max_{j < k \le i}\set{a_k}} $$

单调栈的使用与单调队列基本类似：

	单调栈	单调队列
方程性质	导函数递增、求最大值（P5504 [JSOI2011] 柠檬 - 洛谷），或者导函数递减、求最小值	函数递增、求最小值（P10977 Cut the Sequence - 洛谷），或者导函数递减、求最大值（P10978 Fence - 洛谷）
决策性质	决策 $j$ 总是离 $i$ 越近越合法	决策 $j$ 总是离 $i$ 越远越合法

斜率优化

对于状态转移方程模型： $$ f(i) = \max_{L(i) \le j \le R(i)}\set{f(j) + val(i,j)} $$ 且 $val(i,j)$ 中存在与 $i, j$ 同时相关的项，可以考虑使用线性规划建模，并用单调队列维护下凸壳（上凸壳）以缩小决策范围。

【紫色】P3195 [HNOI2008] 玩具装箱 - 洛谷状态转移方程如下： $$ f(i) - t_i^2 + 2t_i(L+1) - (L+1)^2 = \min_{0 \le j < i}\set{f(j) + t_j^2 + 2t_j(L+1-t_i)} $$ 【紫色】P5785 [SDOI2012] 任务安排 - 洛谷状态转移方程如下： $$ f(i) - \text{sum}T_i \times \text{sum}C_i - S \times \text{sum}C_n = \min_{0 \leq j < i} \set{ f(j) - \text{sum}T_i \times \text{sum}C_j - S \times \text{sum}C_j} $$ 【黑色】P3571 [POI 2014] SUP-Supercomputer - 洛谷计算公式如下： $$ f(i) = \max_{h}\set{h + \lceil \frac{s_{h+1}}{i}\rceil} = \max_{h}\set{\lceil \frac{ih + s_{h+1}}{i}\rceil} $$

四边形不等式优化

对于状态转移方程模型： $$ f(i) = \max_{L(i) \le j \le R(i)}\set{f(j) + val(i,j)} $$ 若 $val(i,j)$ 满足四边形不等式： $$ \forall a \le b \le c \le d. val(a,d) + val(b,c) \ge val(a,c) + val(b,d) $$ 则 $f(i)$ 具有决策单调性，即 $p(i)$ 随 $i$ 的增加而单调不减，其中 $p(i)$ 表示状态转移时关于 $i$ 的决策，即 $$ p(i) = \arg\max_{0 \le j < i}\set{f(j) + val(i,j)} $$

虚假的单调性：证明其满足四边形不等式然后推导单调；

真正的单调性：暴力打印 $p(i)$ 然后找规律发现单调性。

【紫色】P1912 [NOI2009] 诗人小G - 洛谷 $$ f(i) = \min_{0 \le j < i}\set{f(j) + |s_i - s_j + i - j - 1 - L|^P} $$ 其中 $$ val(i,j) = |s_i - s_j + i - j - 1 - L|^P $$ 满足四边形不等式。

【紫色】P4767 [IOI 2000] 邮局加强版 - 洛谷 $$ f(i,j) = \min_{0 \le k < i}\set{f(k,j-1) + w(k+1,i)} $$ 其中， $$ w(l,r) = w(l,r-1) + X_r - X_{mid} $$ 满足四边形不等式。