详细揭秘：区间 DP 小计

· · 算法·理论

状态设计

例：沉玉谷

$n\le 50$。

考虑如何求一个区间的答案：枚举与 l 一同删去的最右的小球。不相交区间之间没有影响，所以还要多一维表示取了几次。

设 f_{l,r,k} 表示区间 [l,r] 取 k 次取完的方案数，g_{l,r,k} 表示在 c_l=c_r 的情况下，区间 [l,r] 取 k 次，不取 l,r 且剩下的小球颜色均与 c_l 相同的方案数。

g_{l,r,k}=\sum_{p=l}^{r-1}[c_l=c_p]\sum_{i=0}^{k}g_{l,p,i}f_{p+1,r-1,k-i}\binom{k}{i} f_{l,r,k}=\sum_{p=l}^{r}[c_l=c_p]\sum_{i=1}^{k}g_{l,p,i-1}f_{p+1,r,k-i}\binom{k}{i}

时间复杂度 O(n^5)。

例：括号序列

一个括号串由 (、)、* 三种字符构成，给定一个常数 k，按如下的方法定义合法括号串：

  • 空串为合法括号串；
  • 设 A,B 均为合法括号串，S 为 * 重复不超过 k 次得到的串，则 (A)、(AS)、(SA)、AB、ASB 均为合法括号串。

给定一个长为 n 的包含 (、)、*、? 四种字符的字符串，求有多少种将所有字符 ? 替换为 (、)、* 的方案数使得其为合法括号串。

合法的括号串必然形如 (A)*(B)***(C)**(D)，其中每个 * 连续段的长度均小于等于 k。

设 f_{l,r,0/1/2/3} 分别表示 [l,r] 得到 A，(A)，*A，A* 的方案数。注意到 0 状态包含 1 状态。

有两种转移，第一种转移为在外加括号，则当 l,r 分别可以为 (、) 时有：

f_{l,r,0/1}\gets f_{l+1,r-1,0}+f_{l+1,r-1,2}+f_{l+1,r-1,3}+[\text{chk}(l+1,r-1)]

其中 [\text{chk}(l,r)] 表示 [l,r] 是否能成为 S。

第二种转移为拼接合法括号串，枚举第一个 (A)：

f_{l,r,0}\gets \sum_{k=l}^rf_{l,k,1}(f_{k+1,r,0}+f_{k+1,r,2}) f_{l,r,2}\gets \sum_{k=l}^r[\text{chk}(l,k)]f_{k+1,r,0} f_{l,r,3}\gets \sum_{k=l}^r[\text{chk}(k,r)]f_{l,k-1,0}

时间复杂度 O(n^3)。

例：Minimum Sum of Maximums P

有一个长为 n 的序列 a_{1\dots n}，初始有 k 个位置 a_{p_1}\dots a_{p_k} 已经有值，其余位置均无值。此外还有 n-k 个数 b_{1\dots n-k}，你需要将它们放入初始无值的位置并最小化 \sum_{i=1}^{n-1}\max(a_i,a_{i+1})。

最小化 \sum\max(a_i,a_{i+1}) 等价于最小化 \sum|a_i-a_{i+1}|。

令 a_0=a_{n+1}=+\infty，固定的位置将序列划分为若干段，要将剩余的数填进去。

考虑一段内填入的数，一段内填的数必然是有序的，所以只需要考虑给这一段填的数的最小值和最大值，不妨设为 l_i,r_i，设这一段两端固定的数分别为 a_i,b_i(a_i\le b_i)，则这个区间的代价为 r_i-l_i+|a_i-l_i|+|b_i-r_i|。

使用调整法可以说明一定有某种最优方案使得所有的 \bm{[l_i,r_i]} 之间只有相离和包含关系，于是将 b 排序，设计状态 f_{l,r,s} 表示使用 b_{l\sim r} 中的数填满 s 中的段的最小代价，注意可能有未使用的数。设 \text{len}(s) 表示 s 中的段的长度总和。

转移共有三种：

时间复杂度 O(3^kn^2)。

例：史莱姆工厂

有 n 个史莱姆排成一行，其中第 i 个的颜色为 c_i，质量为 m_i。

你可以任意次花费 C 将某个史莱姆的质量增加 1。你可以任意卖出史莱姆，一个质量为 i 的史莱姆有 p_i 的价值。但是在任意时刻，如果有史莱姆的质量达到 k 或以上，这个史莱姆就必须立即被卖掉。

卖掉一个史莱姆之后，它两边的史莱姆会靠在一起。颜色相同的史莱姆靠在一起会融合成一个质量等于它们的质量和的史莱姆。

求出卖掉所有史莱姆最多可以净赚多少。

由于 p_i-C\le p_{i+1}，我们不会在卖出时再增加史莱姆的质量。

设 f_{l,r} 表示 [l,r] 的答案，g_{l,r,w} 表示 [l,r] 中卖出一些史莱姆且最终剩余一个包含 l 的质量为 w 的史莱姆的最大获利，h_{l,r,w} 表示 [l,r] 中卖出一些史莱姆且最终剩余一个包含 r 的质量为 w 的史莱姆的最大获利。转移 g_{l,r,w} 时枚举 l 之后第一个合并进来的史莱姆编号：

g_{l,r,w}=\max_{i=l+1,c_l=c_i}^r(f_{l+1,i-1}+g_{i,r,w-m_l})

此外还有不合并的情况即 g_{l,r,m_l}=f_{l+1,r}。h_{l,r,w} 的转移同理。

转移 f_{l,r} 时，如果 \bm{c_l=c_r} 且最后 \bm{l,r} 合并：

f_{l,r}=\max_{i=l,c_l=c_i}^{r-1}\max_{1\le x,y<k}(g_{l,i,x}+h_{i+1,r,y}+p_{x+y})

如果最后 l,r 不合并，注意区间内的史莱姆不能和区间外的合并：

f_{l,r}=\max_{i=l,c_i\ne c_{r+1}\text{ or }c_{i+1}\ne c_{l-1}}^{r-1}(f_{l,i}+f_{i+1,r})

上述几个转移对应的史莱姆删除顺序可以手玩一下。

时间复杂度 O(n^3k^2)。

算法优化

例：Merging Cells P

有 n 个初始大小为 s_{1\dots n} 的细胞从左到右排成一行。当存在多个细胞时，均匀地随机选择一对相邻细胞，其中较大的细胞会吞掉较小的细胞，若它们大小相同则编号较大的细胞会吞掉编号较小的细胞。对 \forall i\in[1,n] 求出最终 i 细胞存活的概率。

区间 DP，但是传统枚举最后一次合并，设计 f_{l,r,i} 表示 [l,r] 得到 i 的概率，时间复杂度 O(n^4)，难以优化。

思维方向是降维或者正难即反。上述做法枚举了最后一次合并，将小区间合并成为大区间。而一个区间得到的细胞大小是固定的，不妨考虑将大区间分裂成为小区间，设计 f_{l,r} 表示最终答案在 [l,r] 的概率。

f_{l,r}=\sum_{1\le k<l}^{s(k,l-1)\le s(l,r)}\dfrac{f_{k,r}}{r-k}+\sum_{r<k\le n}^{s(r+1,k)<s(l,r)}\dfrac{f_{l,k}}{k-l}

时间复杂度 O(n^3)，需要继续优化。显然对于一个区间 [l,r] 只有一个区间内的 k 是合法的，可以双指针求出。以合适的方式选择前缀和、后缀和优化即可做到 O(n^2)。

例：Si

给你一个长为 n 的单调递增的序列 a_{1\dots n}，你需要猜出一个数 x\in[1,n]。每次可以询问一个整数 y，你将会得到 y\le a_x 是否成立，该次询问会造成 |a_x-y| 的代价且你并不知道该代价。求出确定 x 所需要的最小代价和。

将代价中的绝对值拆掉，设 f_{l,r,c} 表示已经确定 x\in[l,r]，且询问的所有 y 中小于 a_x 的个数减去大于 a_x 的个数为 c。则 f_{i,i,c}=ca_i，转移为：

f_{l,r,c}=\min_{k=l}^{r-1}\min_{y=a_k+1}^{a_{k+1}}\max(f_{l,k,c-1}+y,f_{k+1,r,c+1}-y)

其中对于单个 k 其对应的最小 y 显然可以 O(1) 计算。而经过尝试，c 的绝对值不会超过 O(\log v)，于是我们得到了一个 O(n^3\log v) 的算法。

考虑决策单调性，归纳易证 f_{l+1,r,c}\le f_{l,r,c}\le f_{l,r+1,c}，于是我们可以证明 f_{l,r,c} 的决策点 \text{opt}_c(l,r) 满足 \text{opt}_c(l,r-1)\le\text{opt}_c(l,r)\le \text{opt}_c(l+1,r)。直接使用决策单调性优化便可做到 O(n^2\log v)。