连续段 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\)。
剩余空位数为 \(l - k\)，需分配到 \(n+1\) 个空隙中（包括两端），方案数为：
\[\binom{l - k + n}{n}
\]
最终答案：
\[\text{ans} = \sum_{k} dp_{n,1,k} \times \binom{l - k + n}{n}
\]
五、总结
| 操作 | 转移形式 | 系数 |
|---|---|---|
| 新建段 | \(dp_{i+1,j+1}\) | \(j+1\) |
| 扩展段 | \(dp_{i+1,j}\) | \(2\times j\) |
| 合并段 | \(dp_{i+k,j-1}\) | 依题意（如 \(j-1\) 或 \(2\times (j-1)\)） |
连续段 DP 适用于：
- 序列中元素形成若干连续块的构造问题
- 操作与“相邻关系”、“自动填充”相关的问题
- 需处理“段数”、“长度”、“空隙”等状态的问题
通过排序、插板法、组合数学等技巧，可进一步扩展其应用范围。