区间 DP

David_Mercury · 2023-07-11 14:20:41 · 个人记录

一、概念 \& 思想

区间 DP 是以区间为状态的一种 DP。

其核心思想在于：大区间划分为小区间，从小区间向大区间推导信息。类似于有分治性质的一些树形结构。

一般我们以区间长度为阶段，区间端点为状态，划分点的枚举为决策。

二、应用

• P1880 [NOI1995] 石子合并 \& P1063 [NOIP2006 提高组] 能量项链 \& P3205 [HNOI2010] 合唱队 \& P4342 [IOI1998] Polygon

  这些都是以决定合并顺序为核心的区间 DP。

• P3147 [USACO16OPEN] 262144 P

  第一眼猜想为直接区间 DP。显然，O(n^3) 复杂度无法承受。

  数据范围 262144 一看就不对劲，联想本题神似 2048 的玩法，猜想与 2 的次幂有关。经检验，2^{18} = 262144。可以知道，合并的最大值为 40+18 = 58。

  如此小的数据，一定要拿来利用。想到枚举最大值，检验能否合成。

  再重新考虑区间 DP。发现对于每一个区间左端点，只有唯一的区间右端点可以合成一个特定值。因此运用区间拆分、类似倍增 dp 的思想，设当前值为 i，区间左端点为 l，区间右端点为 f[i][l]，则有 f[i][l] = f[i-1][f[i-1][l]+1]。

• P4302 [SCOI2003] 字符串折叠 \& P2470 [SCOI2007] 压缩 \& 串折叠 Folding \& P2400 秘密文件

  这些都是区间 DP 的一种经典应用——字符串压缩问题。

  它们的共同关键在于预处理：只要某子段的右侧有一相等子段，就可以压缩。

  这种题的细节一般也比较繁琐，要千万小心。还要注意压缩后新增字符造成的影响。

• P3205 [HNOI2010] 合唱队 \& P1220 关路灯

  此二者为基于端点的区间 dp。共同点为：拓展了 0,1 一维表示左右端点的状态。

• P4170 [CQOI2007] 涂色 \& P3847 [TJOI2007] 调整队形

  前一道题对于“一次涂色”的处理很巧妙：若区间左右端点颜色相等，那么可以看作一次涂完的，涂 [l, r] 的方案可直接看作 [l+1, r] 或 [l, r-1] 的。那么，要是中间也有可看作一起涂的怎么办？可以注意到，这实则是有决策包容性的——这在之前的小区间里已经被处理过了！

  后一道题有一点相似的思想。将状态设计为使 [l, r] 对称的调整次数，就可以同样根据区间左右端点是否相等来判断转换方法。

  这两道题再次提示我们：关注左右端点之间的关系很重要。

• P6563 [SBCOI2020] 一直在你身旁

  这道题好的地方在于告诉我们区间 dp 本质上是小区间先于大区间计算，写法可以调整（循环不必 len 再 l，可以 r 再 l）。分析详见：数据结构优化 dp。