概要
主讲教师：长沙市雅礼中学 屈运华
内容：动态规划常见模型及各种优化
区间 DP
NOI1995 石子合并
Description
见题面。
Solution
设 \(f_{i, j}\) 合并第 \(i\) 堆到第 \(j\) 堆的最小花费。
则显然有:
\[f_{i, j} = \min_{i \le k < j}\{f_{i, k} + f_{k, j} + w_{i, j}\} \]枚举区间长度，再枚举起点，计算出终点，然后再枚举中间点进行转移。
复杂度 \(\mathcal O(n^3)\)。
例题 1
Description
给定两个颜色序列 \(A, B\)，一次只能选择一种颜色粉刷一个连续的段，求把 \(A\) 刷成 \(B\) 的最少粉刷次数。
Solution
待填。
例题 2
Description
给定一个序列 \(d\)，通过一个栈重排 \(d\) 中的元素顺序，最小化
\[\sum_{i = 1} ^ {n} (i - 1) \cdot d_i \]的值。
Solution
待填。
二维区间 DP
例题 3 CF1199 F
Description
给定一个初始矩阵，这个矩阵上有些位置是黑色，有些位置是白色，每次可以花费一定代价将一个矩形区域令其全部变为白色，求把整个矩形变为白色的最小代价。
Solution
设 \(f_{x_1, y_1, x_2, y_2}\) 表示完成左上角为 \((x_1, y_1)\)，右下角为 \((x_2, y_2)\) 的矩形的最小代价。
显然有:
横向上：
\[f_{x_1, y_1, x_2, y_2} = \min_{x_1 \le k_x < x2}\{f_{x_1, y_1, k_x, y_2} + f_{k_x + 1, y_1, x_2, y_2}\} \]纵向上同理。
复杂度 \(\mathcal O(n^6)\) ？
区间 DP 的四边形不等式优化
四边形不等式：
设 \(w\left(i, j\right)\) 是定义在整数集合上的二元函数，如果对任意整数 \(a \le b \le c \le d\)，都有 \(w\left(a, c\right) + w\left(b, d\right) \le w \left(a, d\right) + w\left(b, c\right)\) 则称 \(w\left(i, j\right)\) 满足四边形不等式。
区间 DP 在某个状态下的答案如果满足四边形不等式，则可以证明“中转点”的位置可以用四边形不等式优化。（这句话写得好糟糕）
状态压缩 DP
例题 AcWing 291 poj2411 - 蒙德里安的梦想
Description
求一个矩形内可以用 \(2 \times 1\) 的矩形划分成的方案数。
Solution
维护轮廓线，设 \(f_{i, j, S}\) 表示决策进行到 \(\left(i, j\right)\) 位置，当前轮廓线状态为 \(S\) 的方案总数。
用 \(1\) 表示横向方块的左半部分，用 \(2\) 表示纵向块的上半部分，枚举状态进行转移，复杂度 \(\mathcal O(2^{2n}n^2)\)。
单调队列优化 DP
例题 1 修剪草坪
Description
给定一个权值序列 \(a\), 在 \(a\) 中选取若干个连续段，每个段的长度都不超过给定参数 \(k\)，最大化段内选择的权值之和。
Solution
设 \(f_{i, 0/1}\) 表示前 \(i\) 个数中其中第 \(i\) 个数不选/选的最大答案。
则显然有:
\[f_{i, 0} = \max\{f_{i - 1, 0}, f_{i - 1, 1}\}\\ f_{i, 1} = \max_{i - k \le j \le i - 1}\{f_{j, 0} + s_i - s_{j}\} \]其中 \(s\) 是前缀和，可以预处理实现。
发现 \(s_i\) 与 \(\max\) 运算无关，可以提到 \(\max\) 外面。
剩下的 \(f_{j, 0} - s_{j}\) 显然可以单调队列维护。
因此可以单调队列优化。
\(\mathcal O(n^2) \to \mathcal O(n)\)。
优化多重背包
模板题 AcWing 6 多重背包问题 III
Description
给定 \(n\) 种物品，每种物品有 \(c_i\) 个，价值为 \(v_i\)，体积为 \(w_i\)。给定一个背包体积 \(V\)，求在满足所选物品的总体积不超过 \(V\) 的情况下最大化价值和。
Solution
这题连二进制优化的 \(\log\) 都卡，因此需要单调队列优化。
对于第 \(i\) 种物品，其体积为 \(w_i\)，发现对于某个背包体积为 \(V_0\) 的状态下的答案，它只能由第 \(i - 1\) 种物品中体积为 \(V_0 - k \cdot w_i(0 \le k \le \min\{c_i, \lfloor\frac{V_0}{w_i}\rfloor\})\) 的状态转移得到。
发现可以将状态按照 \(V_0 \bmod w_i\) 的余数进行分组，每组中的转移互不影响。
因此可以开 \(w_i\) 个单调队列，每个优化其按余数分组后相应组的转移。
每个状态也只有可能进入其相应组的单调队列一次。因此对于每个组转移的复杂度是 \(\mathcal O(V)\) 的。
故总复杂度为 \(\mathcal O(nV)\)。
斜率优化
斜优/se