DP 常见优化技巧

发表于 2025-06-12 更新于 2025-06-21 分类于南京外国语学校 2025 Summer NOI-集训讲义， 20250708-DP 专题阅读次数：
本文字数： 1.8k 阅读时长 ≈ 2 分钟

摘要

2 蓝 5 紫 4 黑

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

倍增优化

【蓝色】P2106 Sam 数 - 洛谷

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

TODO：【紫色】P1357 花园 - 洛谷

单调队列优化

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

状态转移集合是一个单调队列，如果 $j_{2}$ 比 $j_{1}$ 更容易符合转移条件，且收益更大，那么 $j_{1}$ 应该出列。

对于状态转移方程模型：

f (i) = max_{L (i) \leq j \leq R (i)} {f (j) + v a l (i, j)}

且 $v a l (i, j)$ 的每一项仅与 $i, j$ 其中一个有关，可以使用单调队列维护可行决策以缩小决策范围。

【蓝色】P10978 Fence - 洛谷状态转移方程如下：

f (i, j) = max {\begin{matrix} f (i - 1, j) \\ f (i, j - 1) \\ max_{j - L_{i} \leq k < j} {f (i - 1, k) + p_{i} \times (j - k)} & j < S_{i} \end{matrix}}

【紫色】P10977 Cut the Sequence - 洛谷状态转移方程如下：

f (i) = min_{0 \leq j < i \land \sum_{k = j + 1}^{i} a_{k} \leq M} {f (j) + max_{j < k \leq i} {a_{k}}}

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

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

斜率优化

对于状态转移方程模型：

f (i) = max_{L (i) \leq j \leq R (i)} {f (j) + v a l (i, j)}

且 $v a l (i, j)$ 中存在与 $i, j$ 同时相关的项，可以考虑使用线性规划建模，并用单调队列维护下凸壳（上凸壳）以缩小决策范围。

【紫色】P3195 [HNOI2008] 玩具装箱 - 洛谷状态转移方程如下：

f (i) - t_{i}^{2} + 2 t_{i} (L + 1) - (L + 1)^{2} = min_{0 \leq j < i} {f (j) + t_{j}^{2} + 2 t_{j} (L + 1 - t_{i})}

【紫色】P5785 [SDOI2012] 任务安排 - 洛谷状态转移方程如下：

f (i) - sum T_{i} \times sum C_{i} - S \times sum C_{n} = min_{0 \leq j < i} {f (j) - sum T_{i} \times sum C_{j} - S \times sum C_{j}}

【黑色】P3571 [POI 2014] SUP-Supercomputer - 洛谷计算公式如下：

f (i) = max_{h} {h + ⌈ \frac{s_{h + 1}}{i} ⌉} = max_{h} {⌈ \frac{i h + s_{h + 1}}{i} ⌉}

四边形不等式

对于状态转移方程模型：

f (i) = max_{L (i) \leq j \leq R (i)} {f (j) + v a l (i, j)}

若 $v a l (i, j)$ 满足四边形不等式：

\forall a \leq b \leq c \leq d . v a l (a, d) + v a l (b, c) \geq v a l (a, c) + v a l (b, d)

则 $f (i)$ 具有决策单调性，即 $p (i)$ 随 $i$ 的增加而单调不减，其中 $p (i)$ 表示状态转移时关于 $i$ 的决策，即

p (i) = \arg max_{0 \leq j < i} {f (j) + v a l (i, j)}

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

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

【紫色】P1912 [NOI2009] 诗人小G - 洛谷

f (i) = min_{0 \leq j < i} {f (j) + | s_{i} - s_{j} + i - j - 1 - L |^{P}}

其中

v a l (i, j) = | s_{i} - s_{j} + i - j - 1 - L |^{P}

满足四边形不等式。

TODO：【紫色】P4767 [IOI 2000] 邮局加强版 - 洛谷

TODO：【黑色】P8864 「KDOI-03」序列变换 - 洛谷

DP 杂题选讲

【紫色】P2470 [SCOI2007] 压缩 - 洛谷

【黑色】P2703 [NOI2006] 千年虫 - 洛谷

TODO：【黑色】P1721 [NOI2016] 国王饮水记 - 洛谷

目前暂无正解：【黑色】P2145 [JSOI2007] 祖玛 - 洛谷

TODO：【黑色】P8275 [USACO22OPEN] 262144 Revisited P - 洛谷

TODO：【黑色】P8194 [USACO22FEB] Phone Numbers P - 洛谷

TODO：【黑色】P12495 [集训队互测 2024] 链覆盖 - 洛谷

TODO：【黑色】P12483 [集训队互测 2024] 人间应又雪 - 洛谷

【黑色】P10197 [USACO24FEB] Minimum Sum of Maximums P - 洛谷