连续段DP如何成？

连续段 DP 总结 一、核心思想 连续段 DP 是一种按元素放置顺序进行 DP 的技巧，常用于处理“序列中元素形成若干连续段”的问题。其核心特点是： 脱离数组构造：先不考虑具体序列位置，只维护“连续段”的数量与状态。 状态设计：通常设 \(dp_{i,j}\) 表示已处理 \(i\) 个元素，形成 \(j\) 个连续段的方案数。 转移方式：通过“新建段”、“扩展段”、“合并段”三种基本操作完成状态转移。 二、通用转移方式 设当前状态为 \(dp_{i,j}\)： 1. 新建一个段 在 \(j+1\) 个空隙中插入新段： \[dp_{i+1,j+1} \gets dp_{i,j} \times (j+1) \] 2. 扩展一个段 在 \(j\) 个段的左右端点中选择一个扩展： \[dp_{i+1,j} \gets dp_{i,j} \times (2 \times j) \] 3. 合并两个段 在 \(j-1\) 个空隙中合并相邻段，需根据题目条件决定合并方式（如间距为 \(2\) 或 \(3\)）： \[dp_{i+k,j-1} \gets dp_{i,j} \times \text{(系数)} \] 三、例题 1：CF1515E Phoenix and Computers 问题简述 有 \(n\) 台电脑，初始全关。 每次可手动打开一台电脑。 若某台电脑左右都已打开，它会自动打开。 问所有电脑最终打开的手动操作顺序方案数。 思路分析 状态设计 设 \(dp_{i,j}\) 表示已进行 \(i\) 次打开（包括手动和自动），形成 \(j\) 个连续段的方案数。 连续段之间至少间隔 \(2\) 个未打开电脑（否则会自动合并）。 转移方式 1. 新建段：在 \(j+1\) 个空隙中插入新段： \[dp_{i+1,j+1} \gets dp_{i,j} \times (j+1) \] 2. 扩展段：在 \(2j\) 个端点位置扩展： \[dp_{i+1,j} \gets dp_{i,j} \times (2\times j) \] 3. 合并段（间距为 \(2\)）： 中间恰好隔 \(2\) 个空位，手动开 \(1\) 个，另 \(1\) 个自动开： \[dp_{i+2,j-1} \gets dp_{i,j} \times (j-1) \times 2 \] 最终答案 \[\text{ans} = \sum_{j} dp_{n,j} \] 四、例题 2：P7967 [COCI2021/2022 #2] Magnet 问题简述 有 \(n\) 个磁铁，半径分别为 \(r_i\)。 有 \(l\) 个空位，每个空位放一个磁铁，相邻空位距离为 \(1\)。 若两个磁铁距离小于某个磁铁的半径，则会被吸引。 求所有磁铁互不吸引的方案数。 思路分析 关键观察 磁铁按半径从小到大排序后处理，保证当前处理的是“最大”的磁铁。 每个磁铁决定其与相邻磁铁的距离。 状态设计 设 \(dp_{i,j,k}\) 表示： 已处理前 \(i\) 个最小磁铁 形成 \(j\) 个连续段 这些段占用的总长度为 \(k\) 转移方式 1. 新建段： \[dp_{i,j,k} \gets dp_{i,j,k} + dp_{i-1,j-1,k-1} \times j \] 2. 扩展段（贴边）： 新增长度 \(a_i\) 有 \(2j\) 个端点可贴 \[dp_{i,j,k} \gets dp_{i,j,k} + dp_{i-1,j,k - a_i} \times (2\times j) \] 3. 合并两段： 新增长度 \(2a_i - 1\) 有 \(j\) 个空隙可合并 \[dp_{i,j,k} \gets dp_{i,j,k} + dp_{i-1,j+1,k - 2\times a_i + 1} \times j \] 插板法分配剩余空位 最终 \(n\) 个磁铁形成 \(1\) 个大段（\(j=1\)），总长度为 \(k\)。