CF1336C Kaavi and Magic Spell
- \(S\) 串两端添加具有区间 dp 的特征。
- \(S \to T\) 的构建一定是从短到长的，考虑区间 dp。
- 设 \(dp_{i, j}\) 表示构建出 \(T : [i, j]\) 的方案数。
- 答案：\(\sum dp_{1, i}\)。
- 转移：
\[dp_{i, j} = dp_{i, j} + dp_{i + 1, j} \ (s_{j - i + 1} = t_i \lor i > m)
\]
\[dp_{i, j} = dp_{i, j} + dp_{i, j - 1} \ (s_{j - i + 1} = t_j \lor i > m)
\]
- 初始状态：\(dp_{i, i} = 2 \times [i > m \lor s_1 = t_i]\)。
P2470 [SCOI2007] 压缩
- \(dp_{i, j}\) 的信息不够，因为 \(R\) 关心上一个 \(M\) 在哪里（可以是 \(0\)）。
- 设 \(dp_{i, j, 0 / 1}\) 表示将区间 \([i, j]\) 的字符压缩且之前是否有 \(M\)。
- 答案：\(\min \{ dp_{1, n, 0}, dp_{1, n, 1} \}\)。
- 转移：
- \(j\) 后面加 \(R\)：
\[dp_{i, j, 0} = \min \{ dp_{i, j, 0}, dp_{i, mid, 0} + 1 \} \ (s_{[i, mid]} = s_{[mid + 1, j]})
\]
- \(j\) 后面不加 \(R\)：
\[dp_{i, j, 0} = \min_{k \in [i, j]} \{ dp_{i, j, 0}, dp_{i, k, 0} + j - k \}
\]
- \(j\) 后面加 \(M\)：
\[dp_{i, j, 1} = \min_{k \in [i, j)} \{ dp_{i, j, 1}, \min \{ dp_{i, k, 1}, dp_{i, k, 0} \} + \min \{ dp_{k + 1, j, 0}, dp_{k + 1, j, 1} \} + 1 \}
\]
- \(j\) 后面不加 \(M\)：
\[dp_{i, j, 1} = \min_{k \in [i, j)} \{ dp_{i, j, 1}, dp_{i, k, 1} + dp_{k + 1, j, 0} \}
\]
- 初始状态：\(dp_{i, i, 0} = 1, dp_{i, i, 1} = 2\)。