「v3」E - 动态规划
E - 动态规划 状态设计
背包问题
- 一般的背包问题,将物品加进背包的顺序与最终的背包无关。
- 在所有物品中删去一个物品,若背包满足可减性,可以考虑退背包;若背包不满足可减性,可以考虑分治。
- 在所有普通物品中仅有一个物品有特殊贡献,可以考虑优先考虑该特殊物品,再考虑其他普通物品。
退背包:在背包问题中,禁用某个物品后修改 dp 数组的操作。只适用于计数类问题(不止 0/1 背包与完全背包,其余计数类问题也有可能进行退背包),不适用于最优化问题。
0/1 背包退背包:
// Join the backpack.
for (int i = m; i >= w; i --) f[i] += f[i - w];
// Exit the backpack.
for (int i = w; i <= m; i ++) f[i] -= f[i - w];完全背包退背包:
// Join the backpack.
for (int i = w; i <= m; i ++) f[i] += f[i - w];
// Exit the backpack.
for (int i = m; i >= w; i --) f[i] -= f[i - w];树形 dp
容量有关节点数的树上背包:\mathcal{O}(n^2)。
void dp(int u) {
sze[u] = 1;
for (v : son[u]) {
for (int i = 0; i <= sze[u] + sze[v]; i ++) g[i] = 0;
for (int i = 0; i <= sze[u]; i ++)
for (int j = 0; j <= sze[v]; j ++)
// f[u][i] merge f[v][j] -> g[i + j] (O(1))
for (int i = 0; i <= sze[u] + sze[v]; i ++) f[u][i] = g[i];
sze[u] += sze[v];
}
}容量有关节点数的树上背包,时间复杂度证明:点 u 对复杂度的贡献是所有满足 \text{LCA}(x, y) = u 的无序点对 (x, y) 的对数,故总时间复杂度为任意点对 (x, y) 的对数,这样的点对有 \mathcal{O}(n^2) 个。
容量有关节点数且不超过 k 的树上背包:\mathcal{O}(nk)。
void dp(int u) {
sze[u] = 1;
for (v : son[u]) {
for (int i = 0; i <= std::min(sze[u] + sze[v], k); i ++) g[i] = 0;
for (int i = 0; i <= std::min(sze[u], k); i ++)
for (int j = 0; j <= std::min(sze[v], k - i); j ++)
// f[u][i] merge f[v][j] -> g[i + j] (O(1))
for (int i = 0; i <= std::min(sze[u] + sze[v], k); i ++) f[u][i] = g[i];
sze[u] += sze[v];
}
}容量有关节点数且不超过 k 的树上背包,时间复杂度证明:对当前的两棵子树 u, v 的 sz_u, sz_v(不妨设 sz_u < sz_v)分类讨论。
- 当 sz_u > k 且 sz_v > k 时。每次合并的复杂度为 \mathcal{O}(k^2),这样的合并不超过 \frac{n}{k} 次,故该部分复杂度为 \mathcal{O}(nk)。
- 当 sz_u \leq k 且 sz_v > k 时。每次合并的复杂度为 \mathcal{O}(sz_u \cdot k),相当于小子树中的每个点都花费 \mathcal{O}(k) 的复杂度加入大子树,由于小子树中的每个点只会发生一次这样的变化,故该部分复杂度为 \mathcal{O}(nk)。
- 当 sz_u \leq k 且 sz_v \leq k 时。每次合并的复杂度为 \mathcal{O}(sz_u \cdot sz_v),相当于 u 的子树中的每个点都花费 \mathcal{O}(sz_v) 的复杂度使得子树大小扩大 sz_v,由于小子树中的每个点扩大的值至多为 k,故该部分复杂度为 \mathcal{O}(nk)。
综上所述,总时间复杂度为 \mathcal{O}(nk)。
连通性计数
连通性计数套路:容斥,枚举与 1 相连的联通块大小。
n 个点的简单有标号无向连通图个数:设 f_i 表示包含 i 个点的简单有标号无向连通图数,g_i = 2^{i(i - 1)/2} 表示包含 i 个点的有标号无向图数,则有
DAG 计数
有标号 DAG 计数套路:考虑一个不一定弱联通的 DAG,将 DAG 视作一个分层图,枚举拓扑序第一层(零入度点)节点数。
- \mathcal{O}(n^3):设 f(i, j) 表示大小为 i 的 DAG,共 j 个零入度点时的方案数。枚举 k 为拓扑序第二层(删去拓扑序第一层后的零入度点)节点数,则
- \mathcal{O}(n^2):设 f(i) 表示大小为 i 的 DAG 的方案数。钦定该 DAG 有 j 个零入度点,则
状压 dp
\mathcal{O}(3^n) 枚举子集:for (int T = S; T; T = (T - 1) & S) 可以无冗余地遍历集合 S 的所有非空子集 T。
for (int S = 1; S < (1 << m); S ++)
for (int T = S; T; T = (T - 1) & S) // f[S] <- f[T]枚举的时间开销为 \sum_{i = 0}^n \binom{n}{i}2^i = 3^n。
轮廓线 dp
轮廓线:在网格图中,若一个锯齿状的折线可以将网格图分割成已考虑与未考虑两类时,则称该折线为轮廓线。
轮廓线 dp:以轮廓线为状态的 dp。
- 从左下角至右上角的轮廓线必有 n 条竖边 m 条横边。用 1 表示竖边 0 表示横边,则一个从左下角至右上角的轮廓线可以被表示为一个有 n + m 位的二进制数,其中必有 n 个 1。状态总数为 \binom{n + m}{n}。
插头 dp
插头:在网格图中,一个格点有上下左右四个方向的插头,若在某方向上能与相邻的格点相连,则称在该方向有插头。
插头 dp:一种逐格转移的状压 dp。设当前转移到格点 (i, j),则状态 S 记录了第 i 行前 j 个点的下插头信息,第 i - 1 行后 m - j 个点的下插头信息,(i, j) 的右插头信息。
Trick
平方
- 设 q_x = r_1 + r_2 + \cdots + r_k 表示在所有方案中选一个方案,这一个方案绘出的图案为第 x 类的方案数之和。
- 则 q_x^2 = \sum_{i = 1}^k\sum_{j = 1}^k r_ir_j 表示在所有方案中选两个方案,这两个方案绘出的图案均为第 x 类的方案数之和。
- 则 \sum q_x^2 表示在所有方案中选两个方案,这两个方案绘出的图案相同的方案数之和。
E - 动态规划 转移优化
矩阵快速幂优化 dp
- 若对于不同的阶段,有相同的转移,则可以考虑矩阵快速幂优化。
- 若对于不同的阶段,有周期性的转移,则可以考虑维护转移矩阵的循环节乘积和转移矩阵的余项乘积。
- 现要求 A \times G^n,其中 A 为 1 \times m 的初始矩阵,G 为 m \times m 的转移矩阵。
- 预处理:G 的 2^i 次幂,即 G^{1}, G^2, G^4, \cdots。
- 询问:将 n 二进制分解,若 n 的第 i 位为 1,则乘上 G 的 2^i 次幂。时间复杂度 \mathcal{O}(m^2 \log n)。
- 现要求 G^n,其中 n 为高精度整数。可以预处理出 G^0, G^1, \cdots, G^{9},递归做十进制快速幂 G^n = \left(G^{\left\lfloor n / 10\right\rfloor}\right)^{10} \times G^{n \% 10}。
单调队列优化 dp
单调队列优化 dp:可用于优化 tD / eD(任意维度)的 dp,一般形式为
其中 A_j 是仅与 j 有关的变量,B_i 是仅与 i 有关的变量。f_i 的最左端合法决策点 l_i 单调不降。
以下讨论以取最大值为例。
- 对于两个决策点 j_1, j_2(j_1 < j_2),若 f_{j_1} + A_{j_1} \leq f_{j_2} + A_{j_2},则决策点 j_2 不劣于 j_1,此时只需要保留决策点 j_2 即可。
- 维护一个单调队列,满足下标 j 递增,数值 f_j + A_j 递减。
- 在计算 f_i 时,不断弹出队首直到 h \geq l_i 为止。
- 在加入决策点 i 时,不断弹出队尾直到 f_t + A_t > f_i + A_i 为止,然后将决策点 i 加入单调队列。
单调队列优化多重背包:对于 c_i 个价值为 v_i 重量为 w_i 的物品,将重量维按照模 w_i 的同余类分类转移,运用单调队列优化。
斜率优化 dp
斜率优化 dp:常用于优化 1D / 1D 的 dp,一般形式为
其中 A_j, C_j 是仅与 j 有关的变量,B_i, D_i 是仅与 i 有关的变量。
以下讨论以取最大值为例。
转化 1:
- 对于决策点 j,转移可以写成 \underline{f_j + A_j}_{\color{red}y} = \underline{-D_i}_{\color{purple}k} \times \underline{C_j}_{\color{red}x} + \underline{f_i - B_i}_{\color{blue}b} 的形式。将决策点 j 视作二维平面上的一点 (C_j, f_j + A_j),将转移视作一条斜率为 -D_i 的直线。现要求一个决策点 (x, y) 使得经过该点的斜率为 k 的直线的纵截距最大。
- 维护关于决策点的上凸壳。查询时在上凸壳上二分,查找第一条斜率 \leq k 的线段。
- 若每次插入的决策点的横坐标 x 有序,每次查询的斜率 k 有序。则可以使用单调队列维护上凸壳,查询时取队头。
- 若每次插入的决策点的横坐标 x 有序,每次查询的斜率 k 无序。则可以使用单调栈维护上凸壳,查询时二分。
- 若每次插入的决策点的横坐标 x 无序,每次查询的斜率 k 无序。则可以使用平衡树动态维护上凸壳。
转化 2:
- 对于决策点 j,转移可以写成 \underline{f_i - B_i}_{\color{blue}y} = \underline{C_j}_{\color{red}k} \cdot \underline{D_i}_{\color{purple}x} + \underline{f_j + A_j}_{\color{red}b} 的形式。
- 将决策点 j 视作二维平面上的一条斜率为 C_j 截距为 f_j + A_j 的直线,将转移视作一个横坐标值 D_i。现要求一个决策点所对应的直线 y = kx + b 使得其在 x_0 处的纵坐标最大。
- 使用李超线段树维护关于决策点所对应的直线。查询时在李超线段树上遍历,查找在 x_0 处的最大纵坐标。
wqs 二分
wqs 二分:常用于优化 2D / 1D 的 dp,其中一个状态维是选取物品个数。设 f(i) 表示恰好(或最多、最少)选取 i 个物品时的答案,则 wqs 二分适用当且仅当 f 为凸函数。
以下讨论以 f 上凸为例。
二分直线的斜率 \mathrm{mid},计算斜率为 \mathrm{mid} 的直线与上凸壳切在哪个点,比较切点的横坐标与目标选取物品个数的大小关系。
二分直线的斜率 \mathrm{mid} 可以看作是将选择物品附加了一个额外代价 \mathrm{mid},故截距 f_x - \mathrm{mid} \cdot x 可以看作是统计了额外代价后得到的答案。当选取物品的额外代价 \mathrm{mid} 增大时,选取物品个数会减小;反之,选取物品个数会增加。
决策单调性优化 dp
决策点(1D / 1D):对于形如 f(i) \gets_{\min / \max} \{f(j) + w(j, i)\} 的 dp,若当 j = k' 时 f(i) 取到最值,则称 k' 是 f(i) 的决策点,记作 k(i)(多个决策点时,取最小决策点)。
决策单调性(1D / 1D):对于形如 f(i) \gets_{\min / \max} \{f(j) + w(j, i)\} 的 dp,若对于任意 i < i' 均有 k(i) \leq k(i'),则称该 dp 具有决策单调性。
决策点(2D / 1D):对于形如 f(i, j) \gets_{\min / \max} \{ f(k, j - 1) + w(k, i)\} 的 dp,若当 k = k' 时 f(i, j) 取到最值,则称 k' 是 f(i, j) 的决策点,记作 k(i, j)(多个决策点时,取最小决策点)。
决策单调性(2D / 1D):对于形如 f(i, j) \gets_{\min / \max} \{ f(k, j - 1) + w(k, i)\} 的 dp,若对于任意 i < i' 均有 k(i, j) \leq k(i', j),则称该 dp 具有决策单调性。
四边形不等式(形式 1):对于任意 i \leq j,均有
四边形不等式(形式 2):对于任意 l' \leq l < r \leq r',均有
决策单调性优化 dp:二分栈
二分栈:使用栈来维护数据,栈中的每一个元素保存一个决策的起始位置与终止位置,这些位置相互连接且依次递增。当插入一个新的决策时,从后往前扫描栈,对于每一个栈中的老决策
- 若在老决策的起始位置,新决策优于老决策,则转折点在老决策的起始位置之前。把老决策的区间合并到新决策中,将老决策退栈。
- 若在老决策的起始位置,老决策优于新决策,则转折点在老决策的起始位置到终止位置中。二分查找转折点,更新老决策的区间,将新决策入栈。
决策单调性优化 dp:分治
分治:对于形如 f(i) \gets_{\min / \max} \{g(j) + w(j, i)\} 的 dp,使用分治来维护数据。
- 设 \mathrm{solve}(l, r, L, R) 表示:已知 k(l), \cdots, k(r) \subseteq [L, R],现在要求 f(l), \cdots, f(r)。
- 取分治重心 \mathrm{mid} = \left\lfloor \frac{l + r}{2} \right\rfloor,显然 k(\mathrm{mid}) \in [L, R],枚举求出 k(\mathrm{mid})。
- 由于决策单调,则 k(l), \cdots , k(\mathrm{mid} - 1) \subseteq [L, k(\mathrm{mid})] 且 k(\mathrm{mid} + 1), \cdots, k(r) \subseteq [k(\mathrm{mid}), R]。调用 \mathrm{solve}(l, \mathrm{mid} - 1, L, k(\mathrm{mid})) 与 \mathrm{solve}(\mathrm{mid} + 1, r, k(\mathrm{mid}), R),将问题变成两个规模更小的子问题。
CDQ 分治:特别地,若是形如 f(i) \gets_{\min / \max} \{f(j) + w(j, i)\} 的 dp,则需要使用 CDQ 分治。
动态 dp
矩阵描述转移:若一个状态可以由其前驱状态的线性组合得到,则可以用广义矩阵乘法描述转移方程。定义广义矩阵乘法为
其中 \bigotimes 有结合律,且 \bigotimes 对 \bigoplus 有分配律。可以证明此时的广义矩阵乘法有结合律。
动态 dp:一种使用数据结构维护转移矩阵的 dp。特别地,如果不带修,可以考虑用倍增维护。
动态 dp 的重链剖分实现:
- 对原树进行重链剖分,将 f_u 分成重儿子的贡献 f_{\mathrm{heavy}_u} 和轻儿子的贡献和 g_u。使用矩阵描述转移 F(u) = F(\mathrm{heavy}_u) \times G(u),则 F(u) 为 F(\varnothing) 乘上 u 所在重链末端到点 u 的矩阵积,使用线段树维护。
- 一次对点 u 的修改,仅改变 \mathcal{O}(\log n) 个节点的 G 矩阵(一个点的 G 矩阵被修改,当且仅当其轻子树内的某个节点被修改)。不断地跳重链,并实时维护每条重链顶端节点 t 的父节点 \mathrm{Fa}_t 的 G_{\mathrm{Fa}_t} 矩阵。
动态 dp 的全局平衡二叉树实现:待填。