E - 动态规划

背包 dp

退背包：在背包问题中，禁用某个物品后修改 dp 数组的操作。

退背包只适用于技术类问题，在最优化问题中不适用。

0/1 背包退背包：

// 加入背包
for (int i = m; i >= w; i --) f[i] += f[i - w];

// 退出背包
for (int i = w; i <= m; i ++) f[i] -= f[i - w];

完全背包退背包：

// 加入背包
for (int i = w; i <= m; i ++) f[i] += f[i - w];

// 退出背包
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)\) 个。

Q.E.D

容量有关节点数且不超过 \(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];
	}
}

证明：对当前的两棵子树 \(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)\)。

Q.E.D

数位 dp

斜率优化 dp

决策单调性优化 dp

子集 dp

\(\mathcal{O}(4^n)\)枚举：

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

\(\mathcal{O}(3^n)\) 枚举：

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

\(\mathcal{O}(2^n n)\) 子集 dp：将一个二进制状态看成一个 \(n\) 维的坐标，相当于是要求满足每个维度的值都小于该坐标对应维度的值的所有坐标的权值和，高维前缀和。

for (int i = 0; i < m; i ++)
    for (int S = 1; S < (1 << m); S ++)
        if (S >> i & 1) // f[S ^ (1 << i)] -> f[S]

DAG 计数

有标号 DAG 计数：考虑一个不一定弱联通的 DAG，将 DAG 视作一个分层图，枚举拓扑序第一层（零入度点）。

\(\mathcal{O}(n^3)\)：设 \(f(i, j)\) 表示大小为 \(i\) 的 DAG，共 \(j\) 个零入度点时的方案数，枚举 \(k\) 为拓扑序第二层（删去拓扑序第一层后的零入度点）节点数，则

\[f(i, j) = \sum\limits_{k = 1}^{i - j} (2^j - 1)^{k}(2^{i - j - k})^j f(i - j, k) \]

\(\mathcal{O}(n^2)\)：设 \(f(i)\) 表示大小为 \(i\) 的 DAG 的方案数，钦定该 DAG 有 \(j\) 个零入度点，则

\[f(i) = \sum\limits_{j = 1}^i (-1)^{j + 1} \binom{i}{j} 2^{j(i - j)} f(i - j) \]

有标号弱联通 DAG 计数：

连通性计数

连通性计数套路：枚举与 \(1\) 相连的连通块大小。

例：包含 \(n\) 个点的简单有标号无向连通图个数。

设 \(f_i\) 表示包含 \(i\) 个点的简单有标号无向连通图数，\(g_i = 2^{i(i - 1)/2}\) 表示包含 \(i\) 个点的有标号无向连通图数，则有

\[f_i = g_i - \sum\limits_{j = 1}^{i - 1} \binom{i}{j} f_{j}g_{i - j} \]

分治 FFT 形式：

\[\frac{f_i}{i!} = \frac{g_i}{i!} - \sum\limits_{j = 1}^{i - 1} \frac{f_{j}}{j!} \frac{g_{i - j}}{(i - j)!} \]

例：包含 \(n\) 个点的连通图，初始无边，每次在 \([1, n]\) 中独立地等概率随机两个点 \((u, v)\)（可以相同），然后在 \(u, v\) 间连一条边，求使得图连通的期望操作次数。

设 \(f_{i, k}\) 表示包含 \(n\) 个点的图，经过 \(k\) 次操作仍不连通的概率，则有

\[f_{i, k} = \sum\limits_{j = 1}^{i - 1}\sum\limits_{k' = 0}^{k} \binom{i - 1}{j - 1} \binom{k}{k'} (1 - f_{j, k'}) \left(\frac{j^2}{i^2}\right)^{k'}\left(\frac{(i - j)^2}{i^2}\right)^{k - k'} \]

标签：sz,简要,OI,int,复杂度,笔记,背包,mathcal,dp
From： https://www.cnblogs.com/cjtcalc/p/16894940.html

OI 简要笔记（持续更新）