区间与环形 DP 入门

1.区间 DP

定义

• 区间类动态规划是线性动态规划的扩展，它在分阶段地划分问题时，与阶段中元素出现的顺序和由前一阶段的哪些元素合并而来有很大的关系。
• 一般区间 DP 的状态都是一个二维的 f_{i,j} 表示将下标位置 i 到 j 的所有元素合并能获得的价值的最大值。
• 由于区间 DP 的状态是区间，所以 DP 时我们要先枚举区间长度，再枚举左端点。
• 一般需初始化区间长度为 1 时的答案。

性质

• 区间 DP 有以下特点：
• 合并：即将两个或多个部分进行整合，当然也可以反过来；
• 特征：能将问题分解为能两两合并的形式；
• 求解：对整个问题设最优值，枚举合并点（有时合并点就是端点则不用再枚举合并点），将问题分解为左右两个部分，最后合并两个部分的最优值得到原问题的最优值。

例题

P1435 [IOI 2000] 回文字串

• 给定一个字符串，求至少插入几个字符能使其成为回文串。
• 字符串长度 $l\leq1000$。
• 此题为区间 DP 模板题。
• 我们将题目与前面的性质对应。
• 设 $f_{i,j}$ 为将区间 $i$ 到 $j$ 变为回文串的最小插入字符数。
• 要知道 $f_{i,j}$，显然可以通过 $f_{i-1,j}$ 与 $f_{i+1,j}$ 合并而来。
• 具体地，当 $s_i=s_j$，$f_{i,j}=f_{i+1,j-1}$。
• 当 $s_i\neq s_j$，$f_{i,j}=\min (f_{i+1,j}+1,f_{i,j-1}+1)$。
• 相当于端点相等时只需将再里面部分变为回文，不等时连带着一段处理后在另一端加一个字符。
• 枚举区间长度与左端点，合并点就是端点。
• 不需要额外枚举合并点，复杂度平方。

P1775 石子合并（弱化版）

• 给定一个数列，将其任意相邻两数合并为两数之和，同时产生该和的代价。
• 问将数列合并为一个数的最小代价。
• 还是来对应一下性质。
• 设 $f_{i,j}$ 为将区间 $i$ 到 $j$ 合并为一个数的最小代价，$sum_i$ 表示一个原数列的前缀和。
• 那么将一个区间合并的答案可以通过两个子区间合并。
• 具体地，枚举合并点 $k$，则 $f_{i,j}$ 就是所有 $f_{i,k}+f_{k+1,j}+sum_{j}-sum_{i-1}$。
• 即枚举每个可能的合并点，代价就是 i 到 k 的数之和与 k+1 到 j 的数之和的和加两个子区间的答案。
• 这题的合并点需要在端点间枚举，故复杂度是立方。

CF607B Zuma

• 给定一个数列，一次可以消除一个回文数列，问消除整个数列需要几次。
• $n\leq500$。
• 发现这个题与回文子串十分相似。只需增加枚举合并点即可。
• 注意预处理两个字符的情况。

P3205 [HNOI2010] 合唱队

• 同样这个题满足可合并性，还是一道板子。
• 由于这一题人从哪边进来是有影响的，我们再增设一维 $1/0$ 来表示这个人是从左边还是右边进来的。
• 然后我们考虑一个人这么才可以从左边进。也就是前一个人比他高。而前一个人此时一定在当前队列的左端点或右端点，这也说明了本题只有两个合并点。所以我们只要比较将其与两端比较即可。右边同理。

作业题

• P1140 相似基因（板）
• P4170 [CQOI2007] 涂色
• P4290 [HAOI2008] 玩具取名（多记一维改为那个字母并预处理一下每种字母组合可以变为哪些单个字母）
• P3146 [USACO16OPEN] 248 G（板，注意判一个区间是否合法）
• P4342 [IOI 1998] Polygon（注意乘法可以负负得正，还要记最小值）
• P1220 关路灯

2.环形 DP

定义

• 顾名思义就是处理环上问题的 DP。
• 一般直接断环成链（即将链延长至原来的两倍）即可。
• 断环成链后由于长度扩大，最后的答案一般是要枚举左端点的统计的。
• 因为是一个环相当于任意一个点都可以成为我假定的左端点。
• 还有些题可以直接分类讨论。

性质

• 没啥性质。
• 断环成链后它就是正常的各种 DP，或者找规律也没什么很有标志性的性质。

例题

P1880 [NOI1995] 石子合并

• 题意同前面讲过的弱化版。不同处在于这个是环。
• 断环成链后做法同弱化版。
• 最后别忘枚举左端点。

P1121 环状最大两段子段和

• 给出一段长度为 $n$ 的环状序列 $a$，即认为 $a_1$ 和 $a_n$ 是相邻的，选出其中连续不重叠且非空的两段使得这两段和最大。
• $n\leq 2\times10^5,|a_i|\leq10^4$。
• 此题难以直接使用断环成链，故我们考虑分讨最优解的可能形式。
• 显然最优解有跨过端点与不跨过端点两种形式。
• 对于后一种我们直接做一遍最大两段子段和，后一个考虑做一个最小两段子段和后用总和减去即可。

作业

• P1063 [NOIP 2006 提高组] 能量项链（板）
• P1070 [NOIP 2009 普及组] 道路游戏