区间 DP

概述

• 区间 DP 是以 DP 设计从区间出发为特点的一类 DP。

• 状态设计往往包含 \(l,r\)。

• 初始化通常为 \(dp_{l,l}=w_l\)。

• 转移则不一而同，看下面的详解吧。

• 实现倒是比较统一，比较喜欢用记搜，毕竟记搜（在不考虑进/退函数开销的情况下）比较快，而且好写。否则需要枚举 \(len\)。

• 我们下面主要分四类来谈。

分裂式问题

• 典型代表如 \(\text{P1880 [NOI1995] 石子合并}\)。

• 特点是其 DP 设计往往从“枚举断点把整个区间分成两部分，分别处理后合并”的分治思路出发。

• 状态通常为 \(dp_{l,r}\)，表示处理完毕 \(l\sim r\) 的最大/小价值。

• 初始化通常为 \(dp_{l,l}=w_l\)。

• 状态转移方程通常为 \(dp_{l,r}=\max/\min_{k=l}^{r-1}(dp_{l,k}+dp_{k+1,r}+cal(l,r(,k)))\)。

  • 其中 \(cal(l,r(,k))\) 是可能与 \(k\) 无关，也可能与 \(k\) 相关的一个计算合并价值的函数。

  • 如果与 \(k\) 无关，那么很可能可以使用四边形不等式优化。

  • 也有的题目中 \(k\) 是分水岭，不属于任何一边，如 \(\text{P1040 [NOIP2003 提高组] 加分二叉树}\)。

• 通常复杂度为 \(O(n^3)\)，适用四边形不等式的情况可以 \(O(n^2)\)。

P1880 [NOI1995] 石子合并

• 题意：有 \(n\) 堆石子构成一个环，每次可以取相邻的两堆合并成一堆，并获得两者石子数之和的价值，求合并成一堆的最小/最大价值。石子数显然是正整数。

• 数据范围：\(n\leqslant 10^2\)。可以加强到 \(n\leqslant 5\times 10^2\)，大概？

• 这里要求相邻才能合并，否则可以贪心（Huffman 树，合并果子）。

• 考虑设计 DP：

  • 参看“分裂式问题”。

  • 这里只给出 \(cal\)：\(cal(l,r)=sum(l,r)\)。

• 主要问题就是环，暴力枚举断点破环成链即可。复杂度 \(O(n^4)\)。

• 我可以把序列扩展一倍。复杂度 \(O(n^3)\)。

• 其中的最小值部分符合四边形不等式优化的条件，参看四边形不等式优化，可以做 \(O(n^2)\)。最大值...那边也谈了，总之现在就是没有办法。

P1063 [NOIP2006 提高组] 能量项链

• 题意：

  • \(n\) 个珠子构成一个环，每个珠子有两个参数 \(hd,tl\)，保证 \(tl_i=hd_{i+1}\)，环意义下的。

  • 每次可以合并相邻两个获得一个新珠子 \(hd_i,tl_{i+1}\) 和 \(hd_i\times tl_i\times tl_{i+1}\) 的价值。

  • 求最大价值。

• 数据范围：\(n\leqslant 10^2\)。

• 考虑设计 DP：

  • 参看“分裂式问题”。

  • 这里 \(cal(l,r,k)=hd_l\times tl_k\times tl_r\)，表示分裂成 \((l,k)\) 和 \((k+1,r)\) 的转移系数。

• 扩展一倍的话，\(O(n^3)\)。

P4170 [CQOI2007] 涂色

• 题意：

  • 给出数组 \(a_n,c_n\)，开始时 \(a_i=0\)。

  • 你可以将 \(a_{l\sim r}\) 改为同一个值。

  • 问最少多少次操作后，\(a\) 和 \(c\) 相同。

• 数据范围：\(n\leqslant 50\)。

• 发现这道题看起来怎么看怎么像覆盖式啊。

• 然而事实上不是，考虑 \(121343\) 之类的情况，会发现每次只从两头切显然是错的：你不能复用不代表你的子段不能复用。

• 照旧设计 DP：

  • 状态设计：平凡。

  • 初始化：\(dp_{l,l}=1\)。

  • 状态转移方程：

    • 首先是老一套的 \(dp_{l,r}=\min_{k=l}^{r-1}(dp_{l,k}+dp_{k+1,r})\)。

    • 然后是 \(c_l=c_r\) 时的特殊转移：\(dp_{l,r}=dp_{l+1,r}=dp_{l,r-1}\)。

    • 当这个条件成立的时候，上面那个转移没有必要。

    • 它实际上代表着“早晚要涂左/右边不如多涂一格”。

• 复杂度 \(O(n^3)\)。

P1040 [NOIP2003 提高组] 加分二叉树

• 除输出方案外，平凡。略。

P4342 [IOI1998] Polygon

• 有点抖机灵的一道题，当然，这是因为我没想明白。

• 大体上就是一道不能四边形的石子合并，特色大概是正负变换。

覆盖式问题

• 典型代表如 \(\text{P1220 关路灯}\)。

• 特点是题目往往要求将一个链/环上的所有点覆盖，每个点被覆盖时会有一个 \(f(t)\) 即与被覆盖时间相关的估价函数，求最大/最小价值。

  • 通常情况下，可操作位置是在序列上不断移动的，换言之只能同时操作一处，且由于操作往往不需要代价，可操作位置在已处理区间的端点。

  • 通常需要 \(f(t)\) 是同质的，即每个点的估价函数只能有系数的不同，不能有形式的不同，譬如不能一个是一次函数一个是二次函数。

• 状态通常为 \(dp_{l,r,0/1}\) 表示处理完 \(l\sim r\)，当前在 \(l/r\) 的最大/最小损失，即“没赚到一便士就是亏了一便士”。

• 初始化通常为 \(dp_{s,s}=0\)。

• 这里只给出在 \(l\) 的状态转移方程，在 \(r\) 的可以对称推出：\(dp_{l,r,0}=\max/\min(dp_{l+1,r,0}+cal(rest,l,l+1),dp_{l+1,r,1}+cal(rest,l,r))\)。

  • 其中 \(cal(rest,l,r)\) 是基于尚未覆盖的点的 \(f\)（的系数）和从 \(l\) 到 \(r\) 所用时间来计算损失的函数。

• 通常复杂度为 \(O(n^2)\)。

P1220 关路灯

• 题意：

  • \(n\) 盏路灯排成一溜，各有位置 \(k_i\) 和功率 \(w_i\)，初始时老张在 \(s\)，初始时间为 \(0\)。

  • 每秒老张可以移动 \(1\) 的距离，关灯时间忽略不计，如果第 \(i\) 盏灯在第 \(j\) 秒被关上，那么它会浪费 \(j\times w_i\) 的电。

  • 求最小的总浪费量。

• 数据范围：\(n\leqslant 50\)。应该可以做 \(n\leqslant 10^4\)。

• 考虑设计 DP：

  • 参看“覆盖式问题”。

  • 这里只给出 \(cal\)：\(cal(rest,l,r)=(k_r-k_l) \sum\limits_{i\in rest} w_i\)。

• 复杂度 \(O(n^2)\)。

P2466 [SDOI2008] Sue 的小球

• 略，只是 P1220 的数据范围放大版罢了。

P4870 [BalticOI 2009 Day1] 甲虫

• 题意：

  • 有 \(n\) 滴价值为 \(m\) 的水滴在数轴上。初始时甲虫在 \(0\)。

  • 每秒甲虫可以移动 \(1\) 的距离，喝水时间忽略不计，如果某个水珠在第 \(t\) 秒被喝到，那么它会贡献 \(\max(0,m-t)\) 的价值。

  • 求最大总价值。

• 数据范围：\(n\leqslant 3\times 10^2\)。

• 这里的特殊之处主要在于，不一定要都喝，或者说不会有负贡献。之前的“亏损”算法会出问题。

• 解决办法：提高复杂度！暴力枚举喝哪个区间的所有水滴，然后覆盖式。

• 乍一看是 \(O(n^4)\)，实则不然。枚举了喝的水滴量之后，该轮的所有 DP 复杂度不超过求解 \(dp_{1,n}\) 所需，即不超过 \(\Theta(n^2)\)，故总复杂度为 \(O(n^3)\)。

P1005 [NOIP2007 提高组] 矩阵取数游戏

• 除高精外平凡。略。

P6879 [JOI 2020 Final] スタンプラリー 3

• 抖机灵题。把答案统计放到 dp 的维度上，然后把时间扔到等于号右边，顺推比较好些，其余略。

挂载式问题

• 典型代表如 \(\text{P2135 方块消除}\)。

• 特点是给出一个本质为链表的序列，即消去某段之后其两边的段会拼到一起，基于段计算价值。

• 状态通常为 \(dp_{l,r,k}\) 表示处理完 \(l\sim r+k\) 这一段的最小/最大价值。有时为了节约状态，会要求挂载部分和 \(r\) 有某种同质性。

• 初始化为 \(dp_{l,l,k}=cal(k+1)\)，其中 \(cal\) 是基于段长计算价值的函数。

• 状态转移方程通常为 \(dp_{l,r,k}=\max/\min(dp_{l,r-1,0}+cal(k+1),dp_{l,key,k+1}+dp_{key+1,r-1,0})\)，其中 \(key\in [l,r-1]\) 且 \(c_{key}=c_r\)。

  • 实际意义即把后面那一段消掉或者处理一段以设法拼一个更长的。

  • 通过挂载，解决了序列不断移动拼接的问题。好像也有基于做减法的状态设计，但我不太会...

• 注意，这整个 DP 也可以对称设计（即挂载在 \(l\) 左边）。也有时客观上需要两边都挂，那就辅助维比较多。

• 通常复杂度为 \(O(n^3k)\)，\(k\) 为后面挂着的那个辅助维的大小，有时我们不关心挂了多长的只关心有没有，那就是 \(n^3\)（参看 \(\text{10.25 T2 石头剪刀布}\) 我的愚蠢区间 DP，那个不打算做这种 record 了）。

P2135 方块消除

• 题意：

  • 给出 \(c_n\)，每次可以选择一段 \(c\) 全同的 \(l\sim r\) 将其消除并获得 \(len^2\) 的价值，之后其消失，其左右的连接到一起。

  • 求最大总价值。

• 数据范围：\(n\leqslant 10^3\)，但初始时不同的颜色段数量 \(m\leqslant 50\)。

• 考虑设计 DP：

  • 参看“挂载式问题”。

  • 这里只给出 \(cal\)：\(cal(l,r)=(r-l+1)^2\)。

• 理论复杂度 \(O(n^4)\)，实际上大概在 \(O(m^3n)\) 不到的级别，因为无法跑满，总之是跑得飞快。

• 注意到这里我们要求 \(c_{key}=c_r\) 才允许拼接，事实上，这是因为“不造成更长同色段的拼接操作不必要”。即可以认为是把 \(c\) 不等时的转移省略掉了，因为其在此题下无意义。

P5336 [THUSC2016] 成绩单

• 题意：给出 \(w_n\)，每次可以选相连的一段消掉并付出 \(A+B(\max-\min)^2\) 的代价，其中 \(A,B\) 为常系数。求最小总代价。

• 数据范围：\(n\leqslant 50\)。

• 显然离散化，然后设计 DP 如下：

  • 状态设计：\(dp_{l,r,mn,mx}\) 表示后面挂了 \(mn,mx\) 的一段，把 \(l\sim r\) 及挂载段消完的最小总代价。显然，\(mn,mx\) 就可以代表一段了。

  • 初始化：这里我们采用了比较特殊的方式。方块消除这里的挂载量可以为 \(0\)，但这里如果想表示“没有挂载”则需要额外的辅助维，故我们考虑从 \(dp_{1,n-1,w_n,w_n}\) 开始记搜，于是初始化主要是对 \(l>r\) 的情况做，即 \(dp_{l,r(l>r),mn,mx}=calc(mn,mx)\)。

  • 状态转移：

    • \(dp_{l,r,mn,mx}=\min \begin{cases}dp_{l,r-1,w_r,w_r}+calc(mn,mx) \\ dp_{l,r-1,\min(mn,w_r),\max(mn,w_r)}\\ dp_{l,k-1(k>l),mn,mx}+dp_{k,r-1,w_r,w_r}\end{cases}\)。

  • 分别对应直接消，拼，消一段（\(k\sim r\)）以便于拼。这里要求 \(k>l\) 是因为 \(k=l\) 时消没了，拼啥呀，等价于第一种转移了。

• 复杂度 \(O(n^5)\)，足够通过本题。

笛卡尔树式问题

• 典型代表...我觉得 \(\text{P3592 [POI2015] MYJ}\) 和 \(\text{P5851 [USACO19DEC] Greedy Pie Eaters P}\) 都挺典型的，不过是不同的典型。

• 我们先来谈谈笛卡尔树：

  • 笛卡尔树是一种...相比于“一种数据结构”的 OI Wiki 定义，我认为它更像一种数学模型（即使真的建笛卡尔树，我们也是把它当做一棵图论意义下的树，而非数据结构意义下的树来使用）。

  • 笛卡尔树上的点有两个值 \((k,w)\)。在 \(k\) 意义下，笛卡尔树是二叉搜索树；在 \(w\) 意义下，笛卡尔树是堆。

  • 很像 treap？那就对了。不过我们这里并不是把它作为数据结构来使用。

  • 实际使用中，我们一般把数组下标作为 \(k\)。此时其有着美妙的性质：

    • 任意子树都对应着原序列的连续段。

    • 每个子树的根都是区间最值，并把区间进一步划分为两部分。

  • 这有什么意义呢？嗯...

    • 基于序列可能无法设计的状态，在树上显然好一些——至少我不觉得 tdp 的状态难以设计（和线性之类的比起来）。设计出了状态就万事大吉嘛。

    • 同时，树形具有明显的阶段性和划分性，或者说递归性质？相对来讲比较舒服。

    • 典型代表如 \(\text{P7219 [JOISC2020] 星座 3}\)，当然这是个笛卡尔树重构图（大概？或者该说题意转化？）+线合优化 DP，和我们这里的区间 DP 就没啥关系了。

• 特点是给出很多序列上的区间，每个区间都对序列上的点有一定需求，满足不同的需求有不同的收益，求最大收益。

• 状态通常为 \(dp_{l,r}\) 表示把 \(l,r\) 这段定下来的最大收益。可能有辅助维，当然啦，这是因题而变的。

• 初始化通常为...没有初始化。我们在转移方程那里解释。

• 状态转移方程通常为 \(dp_{l,r}=\max/\min_{k=l}^r(dp_{l,k-1}+dp_{k+1,r}+calc(l,r,k))\)。

  • 其中，\(cal(l,r,k)\) 表示将 \(k\) 处决定的影响。

  • 我们来好好谈谈这个转移。不妨以 MYJ 为例（其的笛卡尔树性显然更明显），随着我们不断把最小值放下，所有含 \(k\) 的区间都要和放下的最小值取 \(\min\)。

  • 但事实上，因为我们放下的最小值越来越大，所以每个区间一定在第一次被影响时就决定了。换言之，对于 \([l_i,r_i]\nsubseteq [l,r]\) 的每个需求区间，其一定包含了以前某次划分的 \(k\)，即更早的最小值——也是更小的最小值。

  • 于是我们看到，对于 \(l,r\) 这个阶段，它将所有 \([l_i,r_i]\subseteq [l,r]\) 且 \(k\in [l_i,r_i]\) 的需求区间解决了。

• 实质上还是在划分区间，但这显然不是分裂式——它的分裂具有明显的 cdq 色彩，即以处理跨过划分界的需求或者说区间为核心。

• 通常复杂度为 \(O(n^3)\)，有时会有奇怪的预处理，各凭本事咯。

P3592 [POI2015] MYJ

• 题意：求 \(\max_{i=1}^m(\min_{j=l_i}^{r_i} a_j\leqslant c_i?\min_{j=l_i}^{r_i} a_j:0)\)，并输出对应的 \(a\) 数组。

• 数据范围：\(n\leqslant 50,m\leqslant 4000\)。

• 还是要从数据范围入手。这个范围怎么看都很 \(O(n^2m\sim n^3m)\)。

• 显然可以对 \(c\) 离散化。

• 强行上 DP！

  • 状态设计：\(dp_{l,r,k}\)，表示 \(l\sim r\) 的最小值为 \(k\) 的情况下的最大总收益。这里的 \(k\) 就是它的特色辅助维，某种意义上是因为不带它没法转移而生的（需要保证笛卡尔树性，我指堆性）。

  • 初始化：...这个...看转移罢。

  • 状态转移方程：\(dp_{l,r,k}=\max_{x\geqslant k}(dp_{l,pos-1,x})+\max_{y\geqslant k}(dp_{pos+1,r,y})+calc()\)，其中 \(calc\) 表示将所有 \([l_i,r_i]\subseteq [l,r] \And pos\in [l_i,r_i]\) 的结算为 \(k\) 或 \(0\)（理由是不被完全包含的早就结算过了）。

• 复杂度 \(O(n^3m)\)。显然这个 \(m\) 用常规手段优化不掉。

• 输出方案可以考虑对每个 \(dp\) 记录 \(\operatorname{argmax}\)，并对 \(dp\) 的后缀和数组也记录 \(\operatorname{argmax}\)。

P5851 [USACO19DEC] Greedy Pie Eaters P

• 题意：

  • 有 \(n\) 个物品，\(m\) 个需求，每个需求会将 \(l_i\sim r_i\) 中还剩下的物品全部取走。

  • 当且仅当某个需求确实取到了至少一个物品，你获得 \(w_i\) 的收益。

  • 规划顺序使总收益最大，输出这个最大总收益。

• 数据范围：\(n\leqslant 300,m\leqslant n^2\)。

• 直接暴力上笛卡尔树式问题的一般 DP 设计。这里仅给出 \(calc\)：

  • \(calc(l,r,k)=\max w_i([l_i,r_i]\subseteq [l,r] \And k\in [l_i,r_i])\)。

• 这里事实上不太满足笛卡尔树的堆性质（即使是转移中的 \(calc\) 也不满足），但笛卡尔树的划分性被很好的彰显出来了：

  • 即，强制结算所有过 \(k\) 的并取最大，因为以后再也不能取了——处理跨界，然后左右递归。

• 复杂度 \(O(n^3)\)。

复杂区间 DP

P7914 [CSP-S 2021] 括号序列

• 题意：

  • 给出一个由 \((,),* ,?\) 组成的字符串，其中 \(?\) 可以被指定为 \((,)\) 或 $* $。

  • 定义合法括号序列如下：

    1. ()、(S) 均是符合规范的超级括号序列，其中 S 表示任意一个仅由不超过 \(\bm{k}\) 个字符 * 组成的非空字符串（以下两条规则中的 S 均为此含义）；

    2. 如果字符串 A 和 B 均为符合规范的超级括号序列，那么字符串 AB、ASB 均为符合规范的超级括号序列，其中 AB 表示把字符串 A 和字符串 B 拼接在一起形成的字符串；

    3. 如果字符串 A 为符合规范的超级括号序列，那么字符串 (A)、(SA)、(AS) 均为符合规范的超级括号序列。

    4. 所有符合规范的超级括号序列均可通过上述 3 条规则得到。

  • 求合法方案数。

• 数据范围：\(n\leqslant 500\)。

• 直接按题意模拟。也许会想到线性 DP 的做法，记录有多少个未匹配的左括号，但不对，因为 (SAS) 并不合法，此时无法知道本层是否放过 $* $。

• 故考虑设计一个非常直白的状态 \(dp_{l,r}\)。

• 发现问题主要在于 2 中的分割（将 AB 中的某一项进一步分裂时，会有阶乘种分裂顺序也即算重阶乘次）。

• 于是考虑一个很经典的做法：强制它从左向右断，断出来的左边不许进一步断，即加一个辅助维。

• 后面的转移主要问题在于 ASB 这里，\(n^4\) 无法接受，用一个类似尺取法的前缀和优化就好了。

• 主体大概是分裂式，不过也有一些从两头消的覆盖式的影子。

UVA1630 串折叠 Folding & P2470 [SCOI2007] 压缩

• 看起来挺相像的两道题，对吧？

• 前者大概是和涂色一样的另类分裂式。简单来说，就是找约数暴力。

• 后者尤其有趣，大概要算覆盖式？至少我的做法，即那个 \(O(n^3)\) 纯状态（指 \(O(1)\) 转移）的做法，是覆盖式的思路。强行邻项转移的典范，“掐头”思想用得很好。

• 等等，我把自己骗了！那个做法的复杂度是 \(O(n^2)\)，摆明了是个线性（\(r\) 总是不变）！

• \(r\) 不变，\(l\) 与 \(pr\) 同构。是的，这是 \(O(n^2)\) 的，这是本质线性的。妙啊！

P3736 [HAOI2016] 字符合并

• 一道被严重低估的紫题，我认为。

• 题意略。

• 首先会很自然地想到挂载一个 \(2^K\) 的 \(sta\)，但显然是假的：操作顺序意义很大，首先可能操作以 \(sta\) 的左端点为右端点的 \(K\) 长区间，进一步地，为了操作这个区间可能要操作更左边但和它相交的区间以便于调整最后这个区间是以什么 \(sta\) 被操作的...

• 故暴力挂载式根本行不通，该问题的合并是“到处都是”的，无法简单挂载在后面。

• 考虑转而强行设计如下的 DP：

  • 状态设计：\(dp_{l,r,sta}\) 表示将 \(l\sim r\) 消成 \(sta\) 的最大总价值，这里 \(sta\) 是一个 \(0\sim 2^{K-1}-1\) 的二进制数。

    • \(sta\) 的哪几位有意义？

    • 从题目出发，可以发现长为 \(len\) 的一段总是会被消成 \((len-1)\bmod (K-1)+1\) 的最终段（毕竟 \(w\geqslant 0\)），故容易计算。

  • 初始化：\(dp_{l,l,a_l}=0,dp_{l,r,sta_{l\sim r}}=0\)，特别地，\(dp_{l,r,sta_{l\sim r}}=v_{sta_{l\sim r}}(r-l+1=K)\)。

  • 状态转移方程：分两种情况讨论。

    • \(sta\) 有不止一位：将最后的序列逆向展开，手推容易发现构成森林结构，换言之各个字符的来源互不相交。于是可以强行“掐头”，即将 \(sta\) 的最高位划出去。注意枚举左区间时应当只枚举能合成长度为 \(1\) 的最终区间的合法长度。

    • \(sta\) 只有一位：暴力枚举所有能消成 \(sta\) 的 \(stan\)，其为一个 \(K\) 位二进制数，然后仿照上面的做法。

• 为什么能过？

• 抱歉，我也不明白。这一算法的纸面复杂度上界是 \(O(n^22^{K-1}\times \dfrac{n}{K}\times (1 \text{ or } 2^{K}))\)，理论上完全没有机会，而许多题解使用的还是非记搜实现。

• 总之，这一 DP 设计中的思路对我们大有裨益：首先找到题目限制剪除无效转移（指 \(\dfrac{}{K}\) 这一部分）并利用其来设计状态（确定 \(sta\) 的哪几位有意义），然后利用森林性质进行邻项转移（在状压-区间混合 DP 中就是“掐头”，\(sta\) 抹一位，区间裂两半）。