第十五章 区间与环形动态规划
区间动态规划，及其变种环形动态规划，这两类动态规划的特点是，囿于问题本身限制，“某类有序事件中前若干个事件的子答案” 不再能支撑状态转移，我们需要去寻找 “从某个元素起到另一个元素结束所包含所有的（连续）元素的子答案” 作为状态。
在这个描述下，每个状态会对应原题序列上的一个区间。区间具有良好的性质：短的区间可以拓宽成长的区间，相同长度的区间互相不包含。这样，可以把所有状态理解成 $\text{DAG}$，即不会有可以互相达到的局面。基于这个原则，可以思考如何构造转移。
区间动态规划
例1：P1435 [IOI2000] 回文字串
对于如何把一个长度为 $n$ 的字符串 $S$ 变成回文串这个问题，可以：
- 先把 $S_{1, n - 1}$ 变成回文串，再把 $S_n$ 接在整个串的左边。
- 先把 $S_{2, n}$ 变成回文串，再把 $S_1$ 接在整个串的右边。
- 如果 $S_1$ 和 $S_n$ 相同，那只要把 $S_{2, n - 1}$ 变成回文串就行了。
for (int len = 2; len <= n; len++) {
for (int i = 1; i <= n; i++) {
int j = i + len - 1;
f[i][j] = std::min(f[i][j - 1], f[i + 1][j]) + 1;
if (s[i - 1] == s[j - 1]) f[i][j] = std::min(f[i][j], f[i + 1][j - 1]);
}
}
例2：P1775 石子合并（弱化版）
一堆石子只能和相邻的石子进行合并操作，这代表某堆石子之可能是一段区间内连续合并的结果。那么可以用一个区间状态 $f_{i, j}$ 来表示合并区间 $[i, j]$ 上所有石子所能产生的最小总代价。获得 $f_{i, j}$ 这堆石子的答案一定需要合并它的两个字区间所代表的石子 $f_{i, k}, f_{k + 1, j} (i \le k \lt j)$，而且这两堆石子的总质量一定是 $[i, j]$ 上所有石子的总质量，记为 $w_{i, j}$，因此只需要最小化 $f_{i, j} = \min_{i \le k \lt j} (f_{i, k} + f_{k + 1, j}) + w_{i, j}$。
for (int len = 2; len <= N; len++) {
for (int i = 1; i + len - 1 <= N; i++) {
int j = i + len - 1;
F[i][j] = inf;
for (int k = i; k <= j; k++) {
F[i][j] = std::min(F[i][j], F[i][k] + F[k + 1][j] + pre[j] - pre[i - 1]);
}
}
}
例3：CF607B Zuma
定义 $f_{i, j}$ 表示将字串 $S_{i, j}$ 清空所需要的最少步数。
- 整个串自身是回文串，可以通过比较 $S_i$ 和 $S_j$ 和 $f_{i + 1, j - 1}$ 判断。
- 可以把区间 $[i, j]$ 分成区间 $[i, k]$ 和 $[k + 1, j]$，分别利用这两个区间点答案。
- 一个可消除串夹在另一个可消除串里。
考察回文串的性质。只要某个串的两端字符相同，那么这两个字符不会给消除这个串造成额外的负担，除非这个串长度为 $2$。
for (int i = 1; i <= n; i++) F[i][i] = 1;
for (int i = 1; i < n; i++) if (C[i] == C[i + 1]) F[i][i + 1] = 1; else F[i][i + 1] = 2;
for (int len = 3; len <= n; len++) for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
if (C[i] == C[j]) F[i][j] = F[i + 1][j - 1];
for (int k = i; k < j; k++) F[i][j] = std::min(F[i][j], F[i][k] + F[k + 1][j]);
}
例4：P3205 [HNOI2010]合唱队
用 $f_{i, j}$ 表示在理想队列中，区间 $[i, j]$ 的方案数。但考虑到每一种状态和前一种状态有关，发现还不够。可以增加一维状态，用 $f_{i, j, 0}$ 表示这个区间中刚刚加入的人是从左边进来的，用 $f_{i, j, 1}$ 表示从右边进来。
对于前者，新加入的人比前一个人矮，前一个人可能在 $i + 1$ 号位置，也有可能在 $j$ 号位置；对于后者，新加入的人比前一个人高，前一个人可能在 $j - 1$ 号位置，也可能在 $i$ 号位置。
对于区间 $[i, j]$ 的方案和应当为 $f_{i, j, 0} + f_{i, j, 1}$，这里发生了重复计数。所以当区间长度是 $1$ 的时候，默认从左边加入队列，只需选择一边进行初始化。
for (int i = 1; i <= n; i++) f[i][i][0] = 1;
for (int len = 1; len <= n; len++) {
for (int i = 1; i + len - 1 <= n; i++) {
int j = i + len - 1;
if (h[j] > h[j - 1]) f[i][j][1] += f[i][j - 1][1];
if (h[i] < h[i + 1]) f[i][j][0] += f[i + 1][j][0];
if (h[i] < h[j]) f[i][j][0] += f[i + 1][j][1];
if (h[j] > h[i]) f[i][j][1] += f[i][j - 1][0];
f[i][j][0] %= mod;
f[i][j][1] %= mod;
}
}
像这样以区间左右端点来描述状态，一个状态由比它更小的其他状态转移而来的动态规划方法被称为区间动态规划。转移时，考虑区间边界上的变化。边界条件一般是最小单位的区间（即 $i = j$ 的情况下）。当不是很好构建转移顺序时，可以考虑使用记忆化搜索实现。
环形动态规划
例5：P1880 [NOI1995] 石子合并
可以证明一定存在一个 “断电” 在某两个相邻的石子中间，对于任意环上的合并方式，都不会跨越这个端点进行合并。因此，可以将这个环破成一个链来处理。
如果每次从环中生成一个新的链，分别进行动态规划，则时间复杂度无法接受。所以可以将这个序列复制一次，变为长度为 $2N$ 的序列。其中每一个长度为 $N$ 的连续子序列都是剪开的一条链。这么做的好处是同时处理多个不同的链的过程，可以共同饮用较小区间的数据以节约时间。
最后还需要再次统计，断电在什么地方时可以得到最大或者最小的答案。
for (int i = 1; i <= 2 * N; i++) f[i][i] = 0;
for (int i = 1; i <= 2 * N; i++) g[i][i] = 0;
for (int len = 2; len <= N; len++) {
for (int i = 1; i <= 2 * N; i++) {
int j = i + len - 1;
if (j > 2 * N) break;
for (int k = i; k < j; k++) {
f[i][j] = std::min(f[i][j], f[i][k] + f[k + 1][j]);
g[i][j] = std::max(g[i][j], g[i][k] + g[k + 1][j]);
}
f[i][j] += b[j] - b[i - 1];
g[i][j] += b[j] - b[i - 1];
}
}
for (int i = 1; i <= N; i++) {
int j = i + N - 1;
f[0][0] = std::min(f[0][0], f[i][j]);
g[0][0] = std::max(g[0][0], g[i][j]);
}
例6：环上最大字段和
有个环状数组，每个位置上有个数字（可正可负）。试最大化环上连续一段数字的和（可以是空段，输出 $0$）。序列长度 $n \le 200000$。
环的常见处理方式是复制一倍，再当成区间问题解决。但复制一倍后虚拟字段经常会超过 $n$，这明显是非法情况。
现在考虑答案的情况：作为答案的字段要么经过 $1 - n$ 的分界线，要么不经过 $1 - n$ 的分界线，刚好是非环上序列的最大字段和。考虑前者答案的性质：最大字段和经过 $1 - n$ 的分界线，那么它在环上的补集恰是非环上序列的最小字段和。
获得了这个巧妙的性质，便可以得知最终答案就是非环情况的最大字段和或者最小字段和的补段和。
for (int i = 1; i <= n; i++) {
sum += a[i];
w1 = std::max(0, w1 + a);
w2 = std::min(0, w2 + a);
mx = std::max(mx, w1);
mn = std::min(mn, w2);
}
mx = std::max(mx, sum - mn);