模型分析

至多一段乘 $x$ → 序列被切成「普通 → 乘 $x$ → 普通」三段（任一段可为空）。

DP 对象与生成方式

以 $i$ 结尾的最大子段和，但要额外记录当前处于第几阶段。$dp[i][0/1/2]$ 三状态递推。$O(n)$。

启示

把"是否进入过某特殊状态"显式编码为状态的一维。

翻转一段 = 允许序列走 1→2→1→2 的四段式。等价于在 $dp[i][1..4]$ 上做状态机转移。

模型转化

"不能出现 ABA" → 等价于：每种字符一旦开始选就必须连续选完，之后不能再回头选。

DP 对象与必要性推导

从左到右逐个字符决策选/不选。需要知道：上一个选的字符是谁（判断能否继续同种），以及历史上已经用过哪些字符（用过就不能再新开）。

$dp[i][last][mask]$ = 前 $i$ 个字符，上一位选的字符为 $last$（0~9），已选字符集合为 $mask$（二进制）。$O(N \cdot 10 \cdot 2^{10})$。

模型分析

$\gcd > 1$ 等价于有共同质因子。转移时不能只看上一个元素是谁——如果 $a_i$ 和 $a_{i-1}$ 不互质但和 $a_{i-2}$ 互质，照样能接在 $a_{i-2}$ 后面。

DP 对象的重定义（核心！）

DP 对象不是"以第 $i$ 个元素结尾"，而是以某个质因子 $p$ 结尾。

$dp[p]$ = 最后一个数含有质因子 $p$ 的最长子序列长度。对每个 $a_i$，枚举其所有质因子 $p$，用 $\max_{q \mid a_i} dp[q] + 1$ 更新所有 $dp[p]$。$O(n\sqrt{a})$ 或 $O(n\log a)$（预处理质因子）。

启示

DP 对象不一定是你第一反应的那个。这是 Step 2 的精髓。

模型转化（关键！）

两个排列的 LCS 可以转化为 LIS。令 $pos[x]$ = $x$ 在 $P_2$ 中的位置。将 $P_1$ 的每个元素替换为 $pos[P_1[i]]$，然后在新序列上求 LIS。$O(n\log n)$。

启示

Step 1 的模型简化——把"两个序列的匹配"变成"一个序列的单调性"。

$dp[len][pos]$ = 以 $pos$ 结尾、长度为 $len$ 的 LIS 个数。BIT（树状数组）每层维护前缀和优化转移。$O(nk\log n)$。

（1）最长不升子序列（LDS），$O(n\log n)$。 （2）Dilworth 定理：偏序集的最小链覆盖 = 最长反链长度 → 求 LIS 长度即可。

模型分析

往左移动 = 字符可以"延后匹配"，即允许跳过前面的字符。若 $s$ 和 $t$ 的多重集不同则无解。

DP 对象

$dp[i][j]$ = $s$ 的前 $i$ 个字符中，有多少个已经被匹配到了 $t$ 的前 $j$ 个。当 $s_i = t_j$ 时可向前匹配；否则要么跳过 $s_i$（往左移），要么 $t_j$ 等待后方字符。$O(n^2)$。

经典双序列 DP。设 $D_{i,j}$ 表示 $A[1..i]$ 和 $B[1..j]$ 的编辑距离。若 $A_i = B_j$ 则 $D_{i,j}=D_{i-1,j-1}$；否则 $D_{i,j}=1+\min(D_{i-1,j},D_{i,j-1},D_{i-1,j-1})$。

$dp[i][j] =$ 以 $A_i, B_j$ 结尾时 $4L_{i,j}-i-j$ 的最大值。

转移：若 $A_i = B_j$，$dp[i][j] = \max(dp[i-1][j-1] + 2,\; 0)$；否则 $dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) - 1$。答案取 $dp$ 表中最大值。

正难则反。设 $T_s$ 为第 $s$ 步到达所有点的总方案数，$R_{s,v}$ 为沿被删边走到 $v$ 的非法方案数，则 $D_{s,v}=T_{s-1}-D_{s-1,v}-R_{s,v}$。$R_{s,v}$ 可枚举被删边求和。$O((n+m)k)$。

模型分析

玩具是有序的 → 按顺序分段即可。不需要考虑排列或子集。

DP 对象

$D_i$ = 前 $i$ 个玩具的最小代价。转移枚举上一段的结尾 $j$：$D_i=\min_j(D_j+C_{j,i})$，其中 $C_{j,i}=(S_i-S_j+i-j-1-L)^2$。做到这里即可，复杂度 $O(n^2)$。

原题优化

单调队列维护下凸壳，斜率优化。$O(n)$。

模型分析

最终每个塔楼是原序列中连续一段。塔楼数量越多，合并次数越少（答案 $= n - k$，$k$ 是最终塔楼数）。目标：最大化 $k$。

换维（核心！）

直接记"上一段的和"作为状态量级太大。改用上一个区间的起始位置间接表示。

$dp[i][j]$ = 末尾为 $i$、当前段起点为 $j$ 时，最多能有几段。转移：枚举下一个段的结尾 $k$，要求 $sum[j..i] \leqslant sum[i+1..k]$。$O(n^2)$。

初始直觉

只记 $dp[l][r]$ = 区间 $[l,r]$ 能合并成的最短长度。但问题来了：什么时候两段可以进一步合并成一段？

状态扩充至封闭

两段能合并 $\iff$ 各自都能合并到只剩一个数，且这两个数相等。所以必须额外记录能合并到只剩一个数时，那个数是多少。

增设 $b[l][r]$ = 区间 $[l,r]$ 若能合并成单独一个数时的值（否则为 0）。当 $dp[l][k] = dp[k+1][r] = 1$ 且 $b[l][k] = b[k+1][r]$ 时，$dp[l][r] = 1$、$b[l][r] = b[l][k] + 1$。$O(n^3)$。

启示

状态不够就扩充，直到关于转移封闭——反复走 Step 2→3。

模型分析

这题不是普通的区间 DP——因为消完左边后，右边可能和更左边的东西连在一起。单靠区间两端的信息不够。

“挂载”状态（核心！）

$dp[l][r][k]$ = 区间 $[l,r]$，且左边还有 $k$ 个和 $a_l$ 相同的字符等着一起消（这些字符来自更左侧，被之前的消除操作"遗留"下来）。最大得分。

转移：（1）先把这额外 $k$ 个和 $a_l$ 一起消掉；（2）在区间内找另一个和 $a_l$ 相同的位置 $m$，把中间消掉，然后把 $a_l$ 的"负载"传递给 $m$。$O(n^4)$。

启示

区间 DP 有时需要让"区间外的信息"穿透边界写入状态。

DP 对象

DP 的对象不是按下标分割，而是一个"在某一位上的数字集合"。

生成方式：按位切分

从最高位（第 29 位）向下递归。设当前位为 $b$。若所有 $a_i$ 在第 $b$ 位上全是 0（或全是 1），则可以选 $x$ 的同位让答案的这一位为 0；否则无论如何这一位答案必定为 1，然后按 0/1 分成两组递归取 $\min$。$O(n\log \max a)$。

启示

分段不一定按下标——按最高位 0/1 切分也是合法的"段"。

断环为链（将数组复制一份接在末尾）。$D_{l,r}=\min_k(D_{l,k}+D_{k+1,r})+S_{l,r}$。$O(n^3)$。

模型分析

只有刷新最大值的元素有限制。非刷新元素只需要老老实实出现在某个已确定的最大值后面即可，谁先谁后无所谓。

只 DP 关键元素

将 $a$ 升序排序。$D_i$ = 以 $a_i$ 作为最后一个"刷新最大值"的元素的方案数。转移：$D_i=\sum D_j\cdot P_{\mathrm{rem}}$，求和范围是所有满足 $2a_j\leqslant a_i$ 的 $j$，其中 $P_{\mathrm{rem}}$ 表示用组合数处理中间的非关键元素。$O(n^2)$。

模型分析

$\sum |p_i - i|$ = 直观上就是每个位置和它的值之间的"距离"。如果按值从小到大插入排列，会有一种优雅的计数方式。

开口贡献法

从小到大插入值 $v = 1, 2, \dots, n$。当前有 $j$ 个"开口"（已经知道这个位置将来要放某个值，但现在还没放）。

$dp[v][j][s]$ = 已放入值 $1 \sim v$，当前 $j$ 个开口，已累积距离和 $s$ 的方案数。插入 $v$ 时有三种操作：

• 放自己位置：开口数不变
• 关闭一个开口：$j$ 减 1，距离累计
• 新开一个开口：$j$ 加 1

$O(n^2 k)$。

启示

排列 DP 不需要知道每个值去了哪个具体位置——"开口数"这种全局汇总就够了。

容斥转化

"恰好 $k$ 个"不好直接数。改为先 DP 算出"至少 $j$ 个好位置"的方案数 $f[j]$，再用二项式反演容斥回恰好：$ans[k] = \sum_{j=k}^n (-1)^{j-k} \binom{j}{k} f[j]$。

DP“至少”

$dp[i][j][0/1][0/1]$ = 考虑到位置 $i$，已钦定 $j$ 个好位置，$i$ 是否已占用、$i+1$ 是否已占用的方案数。注意：好位置的定义是"值 $i$ 放在位置 $i-1$ 或 $i+1$"。$O(n^2)$。

模型分析

多个"极长连续被占用段"之间完全无关——因为没人会跨过空位去选另一段的座位。所以可以分别 DP 一个连续段，最后用组合数把各段合并。

最后一个人切分法（核心！）

考虑一个被占用的连续段 $[l, r]$。找最后一个进入该段的人，他坐在某个位置 $m$。他把该段切成左右两个独立的子段，分别 DP。子段间无关 → 组合数合并。

$dp[i][j]$ = $i$ 个位置、$i$ 个人的段的总占用期望（含方案数），通过枚举最后一个人的位置来转移。$O(n^3)$，优化可至 $O(n^2)$。

启示

第二类方法的典范——找"最后决策点"→ 发现独立性 → 拆分处理。

逐团队处理。团内每个人投出的票的去向可以通过组合数算。把团内投票方案数作为物品，跨团队做背包合并。团队内部：将投票视为排列，最后除以阶乘去重。

按锦标赛层级自底向上处理。$dp[mask]$ 从低层级向高层级合并败者集合。组合数处理层级间的选手分配。$O(n2^n)$。

$dp[mask][last]$ = 已选集合为 $mask$、最后一个选的是 $last$ 的方案数。检查相邻和是否为完全平方数即可转移。$O(2^n n^2)$。

在数组 $a$ 上建笛卡尔树（以最小值为根）。选子序列等价于在笛卡尔树上选一些节点，且每个节点贡献为（自身值 $\times$ 被包含的次数）。DP 对象从排列变成了树。$dp[u][j]$ = $u$ 的子树中选了 $j$ 个点的最大价值。$O(n^2)$。

$dp[u][0/1]$ = 不选/选 $u$ 时，$u$ 的子树的最大总快乐值。选 $u$ 时儿子都不能选；不选 $u$ 时儿子可选可不选（取 $\max$）。$O(n)$。

$dp[u][0]$ = $u$ 所在连通块中黑点数为 0 的方案数；$dp[u][1]$ = 黑点数为 1 的方案数。合并儿子 $v$ 时：若切边，$v$ 必须自己有 1 个黑点；若不切边，$v$ 的黑点数必须为 0。$O(n)$。

树上背包。加一个 0 号虚拟根把森林变成树。$dp[u][j]$ = $u$ 子树中选 $j$ 门课（必须选 $u$）的最大学分。合并儿子：$dp[u][j+k] = \max(dp[u][j] + dp[v][k])$。$O(nm^2)$。

调整法证明无关性（核心！）

关键发现：一旦选定第一步染黑的点（即根），后续操作顺序不影响总分！因为无论什么顺序，每个点染黑时的得分始终等于以根为起点时它的子树大小。

证明：交换相邻两次染色，只有当两个点在不同子树时才会互相影响——但交换前后总得分相同。

退化为选根问题

问题转化为：选根最大化子树大小之和。先 DFS 任选一个根算出初始得分，然后换根：$dp[v] = dp[u] + n - 2\times size[v]$。$O(n)$。

启示

Step 1 决定了整道题的难度——用调整法证明无关性，将复杂的过程问题退化为选根问题。

换根 DP 模板。先任选根（如 1）DFS 得到初始深度和 $dp[1]$。然后换根：当根从 $u$ 移到儿子 $v$ 时，$v$ 子树内所有点深度 -1，其余点深度 +1。$dp[v] = dp[u] + n - 2\times size[v]$。$O(n)$。

先自底向上 DP：$D_u=val_u+\sum_v\max(0,D_v)$，其中 $v$ 枚举 $u$ 的儿子（$val_u$ 为白 +1 黑 -1）。再换根：$ans_v=D_v+\max(0,ans_u-\max(0,D_v))$。$O(n)$。

模型分析

最少跳跃次数 $= \lceil \operatorname{dist}(u, v) / k \rceil$。直接求距离和是容易的，但不能简单除以 $k$——因为上取整会破坏线性性。

按余数分类聚合

按 $\bmod k$ 的余数分类！$f[u][r]$ = $u$ 子树中到 $u$ 距离 $\equiv r \pmod{k}$ 的节点数。$g[u][r]$ = 对应的最少跳跃次数之和。合并子树时向上传递。$O(nk)$。

启示

不能直接聚合的量 → 多分几类，按类分别聚合。

每个人恰讨厌一个人 → 基环树（每个连通块恰有一个环）。在环上断一条边 $(u, v)$，做两次树形 DP：一次强制不选 $u$，一次强制不选 $v$。$dp[node][0/1]$ 为不选/选该点的子树最大战斗力。$O(n)$。

模型分析

不允许线段交叉 → 连边的结构天然是"区间嵌套"的。即若 $i < j < k < l$，不可能同时有连边 $(i, k)$ 和 $(j, l)$。

DP 对象是圆上区间

$dp[l][r]$ = 区间 $[l, r]$ 内的点形成一个连通块的方案数（且最外层连接点必须是 $l$ 和 $r$）。$f[l][r]$ = 区间内任意合法连边方案数。

转移：$dp[l][r] = \sum_{k=l}^{r-1} f[l][k] \cdot dp[k][r]$（枚举 $r$ 最左边的邻居）。$f[l][r] = \sum_{k=l}^{r-1} f[l][k] \cdot dp[k][r]$。$O(n^3)$。

启示

空间的几何限制可以转化为 DP 对象的递归结构。这题的"树"不是输入的一棵树，而是从圆的几何性质中推导出来的。

$D_{l,r}$ = 消除区间 $[l, r]$ 的最少次数。若 $c_l = c_r$，可以"免费"把两边和内层一起消：$D_{l,r}\gets D_{l+1,r-1}$（注意当 $l+1>r-1$ 时就是消掉两个相邻同色珠子）。否则枚举分割点：$D_{l,r}=\min_k(D_{l,k}+D_{k+1,r})$。$O(n^3)$。

$D_{l,r}$ = 涂好区间 $[l, r]$ 的最少次数。若 $a_l = a_r$，则 $D_{l,r}=\min(D_{l+1,r},D_{l,r-1})$——要么涂左边时顺便带右边，反之亦然。否则枚举分割点。与 Zuma 对称。$O(n^3)$。

先预处理每个括号的配对位置 $match[l]$。$dp[l][r][c_l][c_r]$ = 区间 $[l, r]$ 两端颜色分别为 $c_l, c_r \in \{0, 1, 2\}$ 的方案数。

若 $r = match[l]$（$l$ 和 $r$ 配对），则内部区间 $[l+1, r-1]$ 独立处理；否则拆为 $[l, match[l]]$ 和 $[match[l]+1, r]$ 两段拼接。$O(n^2)$。

$D_{l,r}$ = 区间 $[l, r]$ 的最短折叠长度。转移有两种：（1）枚举分割点拼接；（2）判断 $[l, r]$ 能否由 $[l, k]$ 重复若干次构成，若能则用 $D_{l,k}+\mathrm{digit}(cnt)+2$ 更新 $D_{l,r}$（$cnt$ 为重复次数，括号贡献为 2）。$O(n^3)$。

$dp[i][j]$ = 前 $i$ 个村庄建 $j$ 个邮局的最小距离和。一段村庄共享一个邮局时最优位置是中位数。

朴素转移枚举上一段起点，复杂度 $O(n^2k)$，训练版做到这里即可。原题数据需要四边形不等式优化决策单调性，复杂度 $O(nk)$。

从最后一步往前想：最后一个插入的人一定在队伍的两端。$dp[l][r][0/1]$ = 区间 $[l, r]$ 已形成且最后加入的是 $l$（左边，0）还是 $r$（右边，1）的方案数。根据与相邻元素的大小关系转移。$O(n^2)$。

模型分析

有时间维度（每组括号"加入"的时间不同），直接按时间 DP 行不通：正着信息量太大，倒着会拆散同组括号。

找静态锚点：第一组括号

考虑第一组加入的括号（最早插入的）。在最终序列中，它们把序列切成三部分：左边的 ( 前面、两个括号之间、右边的 ) 后面。同组括号必在同一部分。

转化为求方案数：$dp[i][j]$ = 长度为 $i$、当前前缀多余的 ( 数为 $j$ 的方案数。最后用概率公式还原。$O(n^3)$，卷积优化可至 $O(n^2)$。

启示

多维限制下，找一个不变的"锚点"作为递归拆分点。

按表达式层级（优先级）BFS 递推。先算所有单字符表达式（x, y, z），然后逐层通过 NOT、AND、OR 组合出更复杂的表达式。对每个真值表记录最短表达式。$O(t \times 8 \times 2^8)$。

DFS 时维护一个栈（记录左括号的下标）。当遇到右括号时，若栈不空则弹出一个左括号，设它的下标为 $p$，则 $dp[u] = dp[fa[p]] + 1$（以 $u$ 结尾的合法子串数）。回溯时恢复栈。$k_u = k_{fa} + dp[u]$。$O(n)$。

状压 DP。预处理每行合法状态（没有相邻 1）及每种状态放置的国王数。再预处理两行间的兼容性。$dp[i][mask][cnt]$ 逐行递推。合法状态远少于 $2^n$。

攻击范围跨两行 → 状态需记录前两行的部署情况。$dp[i][S_1][S_2]$ = 第 $i$ 行状态为 $S_1$、第 $i-1$ 行状态为 $S_2$ 时的最大炮兵数。滚动数组优化空间。$O(n \times 3^m)$ 或更优。

模型简化（核心！）

最终每种颜色的珠子是连续的一段 → 只需决定 20 种颜色的排列顺序。最少相邻交换次数 = 逆序对数。

换 DP 对象：从珠子到颜色

预处理 $w[i][j]$ = 将颜色 $i$ 的所有珠子全部排在颜色 $j$ 的所有珠子前面时，颜色 $i$ 和 $j$ 之间的逆序对数（$O(20^2 n)$）。

$dp[mask]$ = 已决定排列顺序的颜色集合为 $mask$（二进制），这些颜色排在其它颜色前面的最小逆序总和。转移：枚举下一个要排的颜色 $k \notin mask$，增加 $\sum_{j \in mask} w[j][k]$。$O(20 \times 2^{20})$。

启示

$n$ 很大但颜色很少 → DP 对象从"珠子"换成"颜色"。Step 2 的极致体现。

$dp[mask][last]$ = 从 $mask$ 中编号最小的点出发、以 $last$ 结尾、经过点集为 $mask$ 的简单路径数。枚举下一个邻居扩展路径。当 $last$ 能连回起点且路径长度 $\geqslant 3$ 时计入答案。最终答案除以 2（每条环正反各算一次）。$O(2^n n^2)$。

SOS DP（子集 DP）。$dp[mask]$ = 任意一个"是 $mask$ 的子集"的 $a_j$ 的值（若存在）。从低维向高维递推：$dp[mask] \gets dp[mask \oplus 2^i]$（若 $dp[mask]$ 为空且 $dp[mask \oplus 2^i]$ 有值）。

对每个 $a_i$，答案为 $dp[\sim a_i \And ((1\ll 22)-1)]$。$O(22 \times 2^{22})$。

子集卷积 + FWT。先判断每个子集 $mask$ 是否是合法州：需检查连通性（只需两条及以上不交路径或度数判定）和欧拉回路存在性（每个点度数均为偶数）。

$F_M=\sum_{S\subset M}F_{M\oplus S}\cdot W_S$。按 popcount 分层，每层做 FWT（或 FMT），然后逐位做多项式乘法。$O(n^2 2^n)$。