区间 是什么

关于动态规划，其实说白了，就是一种递推。当我们解决大问题的时候，先把它 分解 为若干个子问题，再把它 合并 成当前所需的结果。有点类似于递归的感觉，而递归会重复计算，普通 与记忆化搜索不会。

而区间 ，就是这类问题中的一小类。在我们的 分解 操作时，它需要取任意区间的子问题结果。这类问题就叫做区间 。

对于大多数问题，区间 的架构像这样： 被拆分为若干个 （其中 ），通过这些小区间计算出来的 值推算 。 而 的两个下标代表一个区间的左端点与右端点。

具体问题具体分析，我们当然需要结合问题来进行学习。然而，区间 是有“套路”的，我们接下来把一个个花里胡哨的题目，透过现象去看它的本质，然后把它们 归类 为一个个套路。

区间 架构

通常，我们在做此类问题时，是由小区间推到为大区间。所以，我们要先枚举小区间，再枚举大区间，也就是 枚举长度 。我们的 顺序应是这样的：

image.png

伪代码：

# 初始化 dp[i][i] 或 dp[i][i-1] 因题而异
for len=start to len=end len++ # 枚举长度，start 和 end 分别为最短与最长的长度
    for i=1,j=len to j=n i++,j++ # 枚举对应长度的区间 (i,j)
        ( for k=i to k=j-1 k++ ) # 可能要枚举中间点
            # 进行 dp 操作

还有一种方法也是可以的，这篇文章中“关路灯”类题目也用了这种枚举方法。（感谢金钩爷 @SharpnessV）

首先我们看这种方法为什么不行：

for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++)
        // dp

假设我们程序运行到 ，转移到区间 和 的时候， 还没有运行。

我们得出结论：将左端点枚举到 的时候，比 编号大的左端点一定要先枚举到。所以一种新的做法出现了：

for(int i=n;i>=1;i--)
    for(int j=i;j<=n;j++)
        //dp

我们倒序枚举左端点，就可以保证 顺序正确。

神奇的“套路”们

石子合并类套路

此类问题，是常见的找中间点 分割的问题。

• 例 ZhimaOI #201 合并石子（未注册 zhimaoi.cn 的人请注册）

首先，对于一个区间 ，我们把这个区间内所有石子给合并起来的上一步是啥？

1. 将区间 之间的所有石子全部合并 （其中 ）；
2. 将区间 之间的所有石子全部合并。

我们将这两次合并的结果相加，再加上 之间所有值的和即可。当然，这个 还得枚举来选择最优的。

得转移方程式：

• 例 Luogu P1880 [NOI1995] 石子合并

和例 似乎是一样的，然而它是一个环。我们的做法是 破环为链 ，将这个数列重复两遍，取区间长度为 的最值，这样“环”就被我们考虑到了。

因为这题和上题相似，所以我只提供这题代码。

• 例 Luogu P3146 [USACO16OPEN]248 G

和上述题目十分相似。切断区间 的 ，如果有 ，那么可以合并。得转移方程式：

• 例 HDU 4283 You Are the One

比较难的题目了。

在区间 内，我们首先确定这个 的不高兴的值。这玩意可以枚举！

假设取中间点 ，区间 的人进栈，显然 在这些人中最后一个出栈，等了 个人，这些人的值我们已经算好了。区间 的人自然需要傻傻地等待 之间的所有人，就是 个人。这个值要加进去。所以 是最小的 （ 表示 这些人的权值和， 为区间内一个数）。

具体看本题提供的代码。

• 例 CodeForces 149D Coloring Brackets

数组要记录区间左右端点的染色情况。

如果左右端点是一对匹配的括号，那么推到 ，再分类讨论。

否则，推到 和 ，其中 是与 匹配的括号。再分类讨论。具体的转移方程不是特别难，根据题意可以自行推导。

提供本题代码。

取一端/两端套路

• 例 POJ 2955 Brackets

这题我是真不知道归 还是归类 ，其实都有。

它和石子合并大致相同。可以枚举 中间点 ，得 。但，要注意，如果左端点与右端点括号匹配，长度可以是抹掉左右端点的值加上 ，因为这对括号可以用了。特判一下即可。

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

取一端的经典问题。从小区间推向大区间。转移方程 会转移到 或者 。也可以是大区间推向小区间： 和 。本题以大区间推向小区间来讲。

问题如何知道一个数字取得时候是第几个取的。如果取的是第 个，则是区间外的数量，即 。

注意这题需要做 次 ，并且需要高精度/__int128。

• 例题 Luogu P3205 [HNOI2010]合唱队

也是取一端的经典问题。但是这题要考虑两种情况，一种是一个区间内最后插入左端点，一个是最后插入右端点。当然一个转移为 ，一个转移为 。在转移过去的时候，左/右端点在符合条件的情况下均可以，需要判断。

• 例题 POJ 3280 Cheapest Palindrome

非常古老的问题了。

如果区间 的左端点与右端点相同，直接推锅给 。

否则分四种情况：

1. 在 前插入 ，那么推锅给
2. 删掉 ，推锅给
3. 在 后面插入 ，那么推锅给
4. 删掉 ，推锅给 。

计算一下每次加上的权值，然后就做完了。

• 例 ZhimaOI #520 队列（未注册 zhimaoi.cn 的人请注册）

恰，很有意思嘛。

首先贪心肯定是不对滴。 ：

4
1 6 1000000 5

我们对于每一个区间 开两个数组，一个记录 当前小明取的情况，一个记录 当前小华取的情况 。值是小明能够得到的最多的和。然后分类讨论：

1. 小明则希望自己能得多的，于是在 和 之间取最大值。注意这里的 是小华取的情况。

2. 小华则希望小明得的少，于是在 与 里面取最小值。注意这里的 是小明取的情况。

因为分小华和小明，所以我们要分两个 数组。

关路灯套路

• 例 Luogu P1220 关路灯

分两种情况：老王在左端点；老王在右端点。转移到的区间决定于老王在的位置。老王这么做显然会让区间外以及现在要关的路灯都等相应的时间。

设 分别为老王在 处，关掉 之间的灯所需最小耗能。转移方程我则以代码形式表示：

f[i][j][0]=min(f[i][j][0],f[i+1][j][0]+(a[i+1]-a[i])*(sum[i]+sum[n]-sum[j]));
f[i][j][0]=min(f[i][j][0],f[i+1][j][1]+(a[j]-a[i])*(sum[i]+sum[n]-sum[j]));
f[i][j][1]=min(f[i][j][1],f[i][j-1][1]+(a[j]-a[j-1])*(sum[i-1]+sum[n]-sum[j-1]))
f[i][j][1]=min(f[i][j][1],f[i][j-1][0]+(a[j]-a[i])*(sum[i-1]+sum[n]-sum[j-1]));

其中，， 则为功率， 为位置。

• 例 ZOJ 3469

和上一题思路一模一样！Code 不给了。

• 例 Luogu P2858 [USACO06FEB]Treats for the Cows G/S

也是关路灯类问题。注意：这题的起点可以是任意位置哦！

设 表示取掉了 之间的零食获得的最大权值。注意我们倒推做， 是第 个零食最后一个拿，长度为 的区间的 是这两个零食最后拿的最大全职。

对于长度为 的区间 ，我们可以求得左/右端点是第 个取的。这样就很好计算了。

“找对象”套路

（相信你现在可以自己推导转移方程了！）

先解释一下：这类题目与三元组有关，所以我们可以给端点 找一个合适的 组成三元组。

• 例 LibreOJ #10149. 「一本通 5.1 例 3」凸多边形的划分

对于区间 ，我们找一个点 与其组成三角形，计算出结果，然后讲区间划分为 与 （画图试一下）。然后就是合并果子了？！

注意：需要使用 __int128。

• 例 POJ 1651 Multiplication Puzzle

表示删掉 之间的区间的数字的最大获得权值。我们找到和 一起删掉的 。

首先要删掉 ，然后删掉 （两个 值加上），再加上 ，就是当前 所得到的权值，枚举 即可。 是中间的切断点。

• 例 HDU 5115 Dire Wolf

肥肠简单，和上一题一样。还是有些代码细节，所以提供本题代码。

涂色套路

• 例 Luogu P4170 [CQOI2007]涂色

如果左右端点相同，涂 的时候可以顺带涂一下 ；涂 的时候可以顺带涂一下 。也就是，一个端点可以忽略。否则，枚举中转点涂。

• 例 HDU 2476 String painter

先考虑空串变为 串。对于区间 ，如果有中转点 ，它的字母等于 ，那么涂 的时候可以顺带涂一下 。区间 再考虑。

但是在 串的基础上就麻烦了。对于一个本来就匹配的字母，我们可刷可不刷。具体的操作，我们可以用 表示前 个字母转换的值。如果 ， 可以是 ；否则仅仅可以是 。

• 例 LightOJ 1422 Halloween Costumes

欢迎大家在 这里 提交。

看着不像涂色，可是它就是涂色！

首先，对于区间 ，我们找到要穿的衣服与 相同的 。我们先转移到区间 ，这个值先加上。要注意：此时穿着的衣服是第 次演出所需衣服，和 相同。我们再加上区间 。为啥是 ？因为 的衣服已经被 准备好了，到时候不断脱衣服直到 露出来。

这篇文章结束了！这是博客版文档，所有参考代码请在 这里 下载，或者登录洛谷，在 云剪切板 中查看。

原文地址

PS:

1. 求区间 DP 好题，本文章会不断更新！