「v3」E - 动态规划

    「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

    容量有关节点数的树上背包:O(n2)\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];
        }
    }

    容量有关节点数的树上背包,时间复杂度证明:点 uu 对复杂度的贡献是所有满足 LCA(x,y)=u\text{LCA}(x, y) = u 的无序点对 (x,y)(x, y) 的对数,故总时间复杂度为任意点对 (x,y)(x, y) 的对数,这样的点对有 O(n2)\mathcal{O}(n^2) 个。

    容量有关节点数且不超过 kk 的树上背包:O(nk)\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];
        }
    }

    容量有关节点数且不超过 kk 的树上背包,时间复杂度证明:对当前的两棵子树 u,vu, v 的 szu,szvsz_u, sz_v(不妨设 szu<szvsz_u < sz_v)分类讨论。

    • 当 szu>ksz_u > k 且 szv>ksz_v > k 时。每次合并的复杂度为 O(k2)\mathcal{O}(k^2),这样的合并不超过 nk\frac{n}{k} 次,故该部分复杂度为 O(nk)\mathcal{O}(nk)。
    • 当 szu≤ksz_u \leq k 且 szv>ksz_v > k 时。每次合并的复杂度为 O(szu⋅k)\mathcal{O}(sz_u \cdot k),相当于小子树中的每个点都花费 O(k)\mathcal{O}(k) 的复杂度加入大子树,由于小子树中的每个点只会发生一次这样的变化,故该部分复杂度为 O(nk)\mathcal{O}(nk)。
    • 当 szu≤ksz_u \leq k 且 szv≤ksz_v \leq k 时。每次合并的复杂度为 O(szu⋅szv)\mathcal{O}(sz_u \cdot sz_v),相当于 uu 的子树中的每个点都花费 O(szv)\mathcal{O}(sz_v) 的复杂度使得子树大小扩大 szvsz_v,由于小子树中的每个点扩大的值至多为 kk,故该部分复杂度为 O(nk)\mathcal{O}(nk)。

    综上所述,总时间复杂度为 O(nk)\mathcal{O}(nk)。

    连通性计数

    连通性计数套路:容斥,枚举与 11 相连的联通块大小。

    nn 个点的简单有标号无向连通图个数:设 fif_i 表示包含 ii 个点的简单有标号无向连通图数,gi=2i(i−1)/2g_i = 2^{i(i - 1)/2} 表示包含 ii 个点的有标号无向图数,则有

    fi=gi−∑j=1i−1(i−1j−1)fjgi−jfi(i−1)!=gi(i−1)!−∑j=1i−1fj(j−1)!gi−j(i−j)!f_i = g_i - \sum\limits_{j = 1}^{i - 1} \binom{i - 1}{j - 1} f_{j}g_{i - j} \\ \frac{f_i}{(i - 1)!} = \frac{g_i}{(i - 1)!} - \sum\limits_{j = 1}^{i - 1} \frac{f_{j}}{(j - 1)!} \frac{g_{i - j}}{(i - j)!}

    DAG 计数

    有标号 DAG 计数套路:考虑一个不一定弱联通的 DAG,将 DAG 视作一个分层图,枚举拓扑序第一层(零入度点)节点数。

    • O(n3)\mathcal{O}(n^3):设 f(i,j)f(i, j) 表示大小为 ii 的 DAG,共 jj 个零入度点时的方案数。枚举 kk 为拓扑序第二层(删去拓扑序第一层后的零入度点)节点数,则
    f(i,j)=∑k=1i−j(ij)(2j−1)k(2i−j−k)jf(i−j,k)f(i, j) = \sum\limits_{k = 1}^{i - j} \binom{i}{j} (2^j - 1)^{k}(2^{i - j - k})^j f(i - j, k)
    • O(n2)\mathcal{O}(n^2):设 f(i)f(i) 表示大小为 ii 的 DAG 的方案数。钦定该 DAG 有 jj 个零入度点,则
    f(i)=∑j=1i(−1)j+1(ij)2j(i−j)f(i−j)f(i) = \sum\limits_{j = 1}^i (-1)^{j + 1} \binom{i}{j} 2^{j(i - j)} f(i - j)

    状压 dp

    O(3n)\mathcal{O}(3^n) 枚举子集:for (int T = S; T; T = (T - 1) & S) 可以无冗余地遍历集合 SS 的所有非空子集 TT。

    for (int S = 1; S < (1 << m); S ++)
        for (int T = S; T; T = (T - 1) & S) // f[S] <- f[T]

    枚举的时间开销为 ∑i=0n(ni)2i=3n\sum_{i = 0}^n \binom{n}{i}2^i = 3^n。

    轮廓线 dp

    轮廓线:在网格图中,若一个锯齿状的折线可以将网格图分割成已考虑与未考虑两类时,则称该折线为轮廓线。

    轮廓线 dp:以轮廓线为状态的 dp。

    • 从左下角至右上角的轮廓线必有 nn 条竖边 mm 条横边。用 11 表示竖边 00 表示横边,则一个从左下角至右上角的轮廓线可以被表示为一个有 n+mn + m 位的二进制数,其中必有 nn 个 11。状态总数为 (n+mn)\binom{n + m}{n}。

    插头 dp

    插头:在网格图中,一个格点有上下左右四个方向的插头,若在某方向上能与相邻的格点相连,则称在该方向有插头。

    插头 dp:一种逐格转移的状压 dp。设当前转移到格点 (i,j)(i, j),则状态 SS 记录了第 ii 行前 jj 个点的下插头信息,第 i−1i - 1 行后 m−jm - j 个点的下插头信息,(i,j)(i, j) 的右插头信息。

    Trick

    平方

    • 设 qx=r1+r2+⋯+rkq_x = r_1 + r_2 + \cdots + r_k 表示在所有方案中选一个方案,这一个方案绘出的图案为第 xx 类的方案数之和。
    • 则 qx2=∑i=1k∑j=1krirjq_x^2 = \sum_{i = 1}^k\sum_{j = 1}^k r_ir_j 表示在所有方案中选两个方案,这两个方案绘出的图案均为第 xx 类的方案数之和。
    • 则 ∑qx2\sum q_x^2 表示在所有方案中选两个方案,这两个方案绘出的图案相同的方案数之和。

    E - 动态规划 转移优化

    矩阵快速幂优化 dp

    • 若对于不同的阶段,有相同的转移,则可以考虑矩阵快速幂优化。
    • 若对于不同的阶段,有周期性的转移,则可以考虑维护转移矩阵的循环节乘积和转移矩阵的余项乘积。
    • 现要求 A×GnA \times G^n,其中 AA 为 1×m1 \times m 的初始矩阵,GG 为 m×mm \times m 的转移矩阵。
      • 预处理:GG 的 2i2^i 次幂,即 G1,G2,G4,⋯G^{1}, G^2, G^4, \cdots。
      • 询问:将 nn 二进制分解,若 nn 的第 ii 位为 11,则乘上 GG 的 2i2^i 次幂。时间复杂度 O(m2log⁡n)\mathcal{O}(m^2 \log n)。
    • 现要求 GnG^n,其中 nn 为高精度整数。可以预处理出 G0,G1,⋯ ,G9G^0, G^1, \cdots, G^{9},递归做十进制快速幂 Gn=(G⌊n/10⌋)10×Gn%10G^n = \left(G^{\left\lfloor n / 10\right\rfloor}\right)^{10} \times G^{n \% 10}。

    单调队列优化 dp

    单调队列优化 dp:可用于优化 ttD / eeD(任意维度)的 dp,一般形式为

    fi=min⁡j∈[li,i−1]/max⁡j∈[li,i−1]{fj+Aj+Bi}f_i = \min\limits_{j \in [l_i, i - 1]} / \max\limits_{j \in [l_i, i - 1]} \{ f_j + A_j + B_i \}

    其中 AjA_j 是仅与 jj 有关的变量,BiB_i 是仅与 ii 有关的变量。fif_i 的最左端合法决策点 lil_i 单调不降。

    以下讨论以取最大值为例。

    • 对于两个决策点 j1,j2(j1<j2)j_1, j_2(j_1 < j_2),若 fj1+Aj1≤fj2+Aj2f_{j_1} + A_{j_1} \leq f_{j_2} + A_{j_2},则决策点 j2j_2 不劣于 j1j_1,此时只需要保留决策点 j2j_2 即可。
    • 维护一个单调队列,满足下标 jj 递增,数值 fj+Ajf_j + A_j 递减。
    • 在计算 fif_i 时,不断弹出队首直到 h≥lih \geq l_i 为止。
    • 在加入决策点 ii 时,不断弹出队尾直到 ft+At>fi+Aif_t + A_t > f_i + A_i 为止,然后将决策点 ii 加入单调队列。

    单调队列优化多重背包:对于 cic_i 个价值为 viv_i 重量为 wiw_i 的物品,将重量维按照模 wiw_i 的同余类分类转移,运用单调队列优化。

    斜率优化 dp

    斜率优化 dp:常用于优化 11D / 11D 的 dp,一般形式为

    fi=min⁡/max⁡{fj+Aj+Bi+CjDi}f_i = \min / \max\{ f_j + A_j + B_i + C_jD_i\}

    其中 Aj,CjA_j, C_j 是仅与 jj 有关的变量,Bi,DiB_i, D_i 是仅与 ii 有关的变量。

    以下讨论以取最大值为例。

    转化 1:

    • 对于决策点 jj,转移可以写成 fj+Aj‾y=−Di‾k×Cj‾x+fi−Bi‾b\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} 的形式。将决策点 jj 视作二维平面上的一点 (Cj,fj+Aj)(C_j, f_j + A_j),将转移视作一条斜率为 −Di-D_i 的直线。现要求一个决策点 (x,y)(x, y) 使得经过该点的斜率为 kk 的直线的纵截距最大。
    • 维护关于决策点的上凸壳。查询时在上凸壳上二分,查找第一条斜率 ≤k\leq k 的线段。
      • 若每次插入的决策点的横坐标 xx 有序,每次查询的斜率 kk 有序。则可以使用单调队列维护上凸壳,查询时取队头。
      • 若每次插入的决策点的横坐标 xx 有序,每次查询的斜率 kk 无序。则可以使用单调栈维护上凸壳,查询时二分。
      • 若每次插入的决策点的横坐标 xx 无序,每次查询的斜率 kk 无序。则可以使用平衡树动态维护上凸壳。

    转化 2:

    • 对于决策点 jj,转移可以写成 fi−Bi‾y=Cj‾k⋅Di‾x+fj+Aj‾b\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} 的形式。
    • 将决策点 jj 视作二维平面上的一条斜率为 CjC_j 截距为 fj+Ajf_j + A_j 的直线,将转移视作一个横坐标值 DiD_i。现要求一个决策点所对应的直线 y=kx+by = kx + b 使得其在 x0x_0 处的纵坐标最大。
    • 使用李超线段树维护关于决策点所对应的直线。查询时在李超线段树上遍历,查找在 x0x_0 处的最大纵坐标。

    wqs 二分

    wqs 二分:常用于优化 22D // 11D 的 dp,其中一个状态维是选取物品个数。设 f(i)f(i) 表示恰好(或最多、最少)选取 ii 个物品时的答案,则 wqs 二分适用当且仅当 ff 为凸函数。

    以下讨论以 ff 上凸为例。

    二分直线的斜率 mid\mathrm{mid},计算斜率为 mid\mathrm{mid} 的直线与上凸壳切在哪个点,比较切点的横坐标与目标选取物品个数的大小关系。

    二分直线的斜率 mid\mathrm{mid} 可以看作是将选择物品附加了一个额外代价 mid\mathrm{mid},故截距 fx−mid⋅xf_x - \mathrm{mid} \cdot x 可以看作是统计了额外代价后得到的答案。当选取物品的额外代价 mid\mathrm{mid} 增大时,选取物品个数会减小;反之,选取物品个数会增加。

    决策单调性优化 dp

    决策点(11D / 11D):对于形如 f(i)←min⁡/max⁡{f(j)+w(j,i)}f(i) \gets_{\min / \max} \{f(j) + w(j, i)\} 的 dp,若当 j=k′j = k' 时 f(i)f(i) 取到最值,则称 k′k' 是 f(i)f(i) 的决策点,记作 k(i)k(i)(多个决策点时,取最小决策点)。

    决策单调性(11D / 11D):对于形如 f(i)←min⁡/max⁡{f(j)+w(j,i)}f(i) \gets_{\min / \max} \{f(j) + w(j, i)\} 的 dp,若对于任意 i<i′i < i' 均有 k(i)≤k(i′)k(i) \leq k(i'),则称该 dp 具有决策单调性。

    决策点(22D / 11D):对于形如 f(i,j)←min⁡/max⁡{f(k,j−1)+w(k,i)}f(i, j) \gets_{\min / \max} \{ f(k, j - 1) + w(k, i)\} 的 dp,若当 k=k′k = k' 时 f(i,j)f(i, j) 取到最值,则称 k′k' 是 f(i,j)f(i, j) 的决策点,记作 k(i,j)k(i, j)(多个决策点时,取最小决策点)。

    决策单调性(22D / 11D):对于形如 f(i,j)←min⁡/max⁡{f(k,j−1)+w(k,i)}f(i, j) \gets_{\min / \max} \{ f(k, j - 1) + w(k, i)\} 的 dp,若对于任意 i<i′i < i' 均有 k(i,j)≤k(i′,j)k(i, j) \leq k(i', j),则称该 dp 具有决策单调性。

    四边形不等式(形式 1):对于任意 i≤ji \leq j,均有

    w(i,j)+w(i+1,j+1)≤w(i+1,j)+w(i,j+1)w(i, j) + w(i + 1, j + 1) \leq w(i + 1, j) + w(i, j + 1)

    四边形不等式(形式 2):对于任意 l′≤l<r≤r′l' \leq l < r \leq r',均有

    w(l′,r)+w(l,r′)≤w(l,r)+w(l′,r′)w(l', r) + w(l, r') \leq w(l, r) + w(l', r')

    决策单调性优化 dp:二分栈

    二分栈:使用栈来维护数据,栈中的每一个元素保存一个决策的起始位置与终止位置,这些位置相互连接且依次递增。当插入一个新的决策时,从后往前扫描栈,对于每一个栈中的老决策

    • 若在老决策的起始位置,新决策优于老决策,则转折点在老决策的起始位置之前。把老决策的区间合并到新决策中,将老决策退栈。
    • 若在老决策的起始位置,老决策优于新决策,则转折点在老决策的起始位置到终止位置中。二分查找转折点,更新老决策的区间,将新决策入栈。

    决策单调性优化 dp:分治

    分治:对于形如 f(i)←min⁡/max⁡{g(j)+w(j,i)}f(i) \gets_{\min / \max} \{g(j) + w(j, i)\} 的 dp,使用分治来维护数据。

    • 设 solve(l,r,L,R)\mathrm{solve}(l, r, L, R) 表示:已知 k(l),⋯ ,k(r)⊆[L,R]k(l), \cdots, k(r) \subseteq [L, R],现在要求 f(l),⋯ ,f(r)f(l), \cdots, f(r)。
    • 取分治重心 mid=⌊l+r2⌋\mathrm{mid} = \left\lfloor \frac{l + r}{2} \right\rfloor,显然 k(mid)∈[L,R]k(\mathrm{mid}) \in [L, R],枚举求出 k(mid)k(\mathrm{mid})。
    • 由于决策单调,则 k(l),⋯ ,k(mid−1)⊆[L,k(mid)]k(l), \cdots , k(\mathrm{mid} - 1) \subseteq [L, k(\mathrm{mid})] 且 k(mid+1),⋯ ,k(r)⊆[k(mid),R]k(\mathrm{mid} + 1), \cdots, k(r) \subseteq [k(\mathrm{mid}), R]。调用 solve(l,mid−1,L,k(mid))\mathrm{solve}(l, \mathrm{mid} - 1, L, k(\mathrm{mid})) 与 solve(mid+1,r,k(mid),R)\mathrm{solve}(\mathrm{mid} + 1, r, k(\mathrm{mid}), R),将问题变成两个规模更小的子问题。

    CDQ 分治:特别地,若是形如 f(i)←min⁡/max⁡{f(j)+w(j,i)}f(i) \gets_{\min / \max} \{f(j) + w(j, i)\} 的 dp,则需要使用 CDQ 分治。

    动态 dp

    矩阵描述转移:若一个状态可以由其前驱状态的线性组合得到,则可以用广义矩阵乘法描述转移方程。定义广义矩阵乘法为

    Ci,j=⨁k=1nAi,k⊗Bk,jC_{i, j} = \bigoplus_{k = 1}^n A_{i, k} \otimes B_{k, j}

    其中 ⨂\bigotimes 有结合律,且 ⨂\bigotimes 对 ⨁\bigoplus 有分配律。可以证明此时的广义矩阵乘法有结合律。

    动态 dp:一种使用数据结构维护转移矩阵的 dp。特别地,如果不带修,可以考虑用倍增维护。

    动态 dp 的重链剖分实现:

    • 对原树进行重链剖分,将 fuf_u 分成重儿子的贡献 fheavyuf_{\mathrm{heavy}_u} 和轻儿子的贡献和 gug_u。使用矩阵描述转移 F(u)=F(heavyu)×G(u)F(u) = F(\mathrm{heavy}_u) \times G(u),则 F(u)F(u) 为 F(∅)F(\varnothing) 乘上 uu 所在重链末端到点 uu 的矩阵积,使用线段树维护。
    • 一次对点 uu 的修改,仅改变 O(log⁡n)\mathcal{O}(\log n) 个节点的 GG 矩阵(一个点的 GG 矩阵被修改,当且仅当其轻子树内的某个节点被修改)。不断地跳重链,并实时维护每条重链顶端节点 tt 的父节点 Fat\mathrm{Fa}_t 的 GFatG_{\mathrm{Fa}_t} 矩阵。

    动态 dp 的全局平衡二叉树实现:待填。