0x57 倍增优化 DP

在0x06节中，我们已经结合递推介绍了倍增思想，请读者回顾。因为动态规划经常采用按阶段的递推形式实现，所以也可以按照类似的方法，使用倍增把阶段的线性增长优化为成倍增长。

事实上，0x06节提到的区间最值问题的ST算法也可以用倍增优化DP的方式理解。在ST算法中， $F[i,j]$ 表示数列A在子区间 $[i,i + 2^j -1]$ 里的最大值，即

$\max_{i \leq k < i + 2^j} \{A_k\}$ 。这个动态规划的“阶段”就是区间的长度（成倍增长），区间的左端点 $i$ 是一个附加维度。因此在 ST 算法的实现中，外层循环为区间长度以 2 为底的对数，内层循环为左端点。在状态转移时，从长度为 $2^{i - 1}$ 的阶段转移到长度为 $2^i$ 的阶段。

在本节中，我们再以两道例题对动态规划中倍增优化的运用进行探讨。

【例题】开车旅行 NOIP2012/CODEVS1199

小A和小B决定利用假期外出旅行，他们将想去的城市从1到 $N$ 编号，且编号较小的城市在编号较大的城市的西边，已知各个城市的海拔高度互不相同，记城市 $i$ 的海拔高度为 $H_{i}$ ，城市 $i$ 和城市 $j$ 之间的距离 $d[i,j]$ 恰好是这两个城市海拔高度之差的绝对值，即 $d[i,j] = \left|H_i - H_j\right|$ 。

旅行过程中，小A和小B轮流开车，第一天小A开车，之后每天轮换一次。他们计划选择一个城市 $S$ 作为起点，一直向东行驶，并且最多行驶 $X$ 公里就结束旅行。小A和小B的驾驶风格不同，小B总是沿着前进方向选择一个最近的城市作为目的地，而小A总是沿着前进方向选择第二近的城市作为目的地（注意：本题中如果当前城市到两个城市的距离相同，则认为离海拔低的那个城市更近）。如果其中任何一人无法按照自己的原则选择目的城市，或者到达目的地会使行驶的总距离超出 $X$ 公里，他们就会结束旅行。

在启程之前，小A想知道两个问题：

1. 对于一个给定的 $X = X_{0}$ ，从哪一个城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值最小（如果小B的行驶路程为0，此时的比值可视为无穷大，且两个无穷大视为相等）。如果从多个城市出发，小A开车行驶的路程总数与小B行驶的路程总数的比值都最小，则输出海拔最高的那个城市。

2. 对任意给定的 $X = X_{i}$ 和出发城市 $S_{i}$ ，求出小A开车行驶的路程总数以及小B行驶的路程总数。

$1 \leq N \leq 10^{5}, 1 \leq M \leq 10^{4}, -10^{9} \leq H_{i} \leq 10^{9}, 0 \leq X_{0} \leq 10^{9}, 1 \leq S_{i} \leq N, 0 \leq X_{i} \leq 10^{9}$ , 数据保证 $H_{i}$ 互不相同。

先预处理出小A和小B从每个城市 $i$ 出发，沿前进方向行驶到的下一个城市，分别记为 $\mathrm{ga}(i)$ 和 $\mathrm{gb}(i)$ 。根据题意， $\mathrm{ga}(i)$ 就等于 $i + 1 \sim N$ 中使 $\mathrm{dist}(i, j)$ 取到最小值的城市 $j$ ， $\mathrm{gb}(i)$ 则等于 $i + 1 \sim N$ 中使 $\mathrm{dist}(i, j)$ 取到次小值的城市 $j$ 。我们已经在第0x13节的例题“邻值查找”中，用平衡树（STL set）和链表两种方法解决了该问题，请读者回顾。

本题有三个关键信息——所在城市、已行驶的天数、A和B各行驶的路程长度。若已知出发城市和天数，就能计算出到达城市和A、B行驶的路程长度，并且天数还能

反映轮到谁开车，因此我们在DP中就把“天数”作为“阶段”，所在城市作为另一维状态，并使用倍增对DP进行优化。

设 $f[i,j,k]$ 表示从城市 $j$ 出发，两人共行驶 $2^{i}$ 天， $k$ 先开车，最终会到达的城市。其中 $k = 0$ 或1，0代表轮到小A先开车，1代表轮到小B先开车。

初值： $f[0,j,0] = \mathrm{ga}(j)$ ， $f[0,j,1] = \mathrm{gb}(j)$ 。

当 $i = 1$ 时，因为 $2^{0}$ 是奇数，所以两人从 $j$ 出发开 $2^{1}$ 天到达的城市，等于 $k$ 先开 $2^{0}$ 天，另一人 $1 - k$ 再开 $2^{0}$ 天到达的城市。

当 $i > 1$ 时，因为 $2^{i - 1}$ 是偶数，所以前后两半路程都轮到 $k$ 先开车。

读者在具体实现时，需要注意 ga、gb 和 $f$ 数组到达的城市超出第 $N$ 个城市的边界情况，这里就不再赘述。

设 $da[i,j,k]$ 表示从城市 $j$ 出发，两人共行驶 $2^{i}$ 天， $k$ 先开车，小A行驶的路程总长度。

初值： $da[0,j,0] = \mathrm{dist}(j,\mathrm{ga}(j))$ ， $da[0,j,1] = 0$ 。

当 $i = 1$ 时， $da[1,j,k] = da[0,j,k] + da[0,f[0,j,k],1 - k]$ 。

当 $i > 1$ 时， $da[i,j,k] = da[i - 1,j,k] + da[i - 1,f[i - 1,j,k],k]$ 。

设 $db[i,j,k]$ 表示从城市 $j$ 出发，两人共行驶 $2^{i}$ 天， $k$ 先开车，小B行驶的路程总长度。

初值： $db[0,j,0] = 0$ ， $db[0,j,1] = \mathrm{dist}(j,\mathrm{gb}(j))$ 。

当 $i = 1$ 时， $db[1,j,k] = db[0,j,k] + db[0,f[0,j,k],1 - k]$ 。

当 $i > 1$ 时， $db[i,j,k] = db[i - 1,j,k] + db[i - 1,f[i - 1,j,k],k]$ 。

上述动态规划算法在 $O(N \log N)$ 的时间内计算出了所有“行驶天数为 2 的整数次幂”的状态。接下来我们考虑问题 $\operatorname{calc}(S, X)$ ，意为“从城市 $S$ 出发最多行驶 $X$ 公里”时，A 和 B 分别行驶了多长的路程。

我们按递减顺序枚举所有2的整数次幂，作为行驶天数，并用动态规划中得到的状态，基于二进制划分思想来拼成 $X$ 。具体来说：

1. 初始化当前城市 $p = S$ ，小A、小B累计行驶路程 $la = 0$ ， $lb = 0$ 。

2. 倒序循环 $i = \log N \sim 0$ 。

3. 对于每个 $i$ ，若两人从 $p$ 出发行驶 $2^{i}$ 天，累计路程仍未超过 $X$ ，即 $la + lb + da[i, p, 0] + db[i, p, 0] \leq X$ ，则令 $la = la + da[i, p, 0], lb = lb + db[i, p, 0], p = f[i, p, 0]$ 。

4. 循环结束后， $la$ 与 $lb$ 即为所求。

枚举起点 $S_{i}$ , 取 A、B 行驶路程比值最小的 $\operatorname{calc}(S_{i}, X_{0})$ , 即可求出原问题一。原问题二就是多次询问 $\operatorname{calc}(S_{i}, X_{i})$ , 也可以直接计算。整个算法的时间复杂度为 $O((N + M) \log N)$ 。

【例题】Count The Repetitions LeetCode466

定义 $\operatorname{conn}(s, n)$ 为 $n$ 个字符串 $s$ 首尾相接形成的字符串，例如：

称字符串 $a$ 能由字符串 $b$ 生成，当且仅当从字符串 $b$ 中删除某些字符后可以得到字符串 $a$ 。例如“abdbc”可以生成“abc”，但是“acbbe”不能生成“abc”。

给定两个字符串 $s_1$ 和 $s_2$ , 以及两个整数 $n_1$ 和 $n_2$ , 求一个最大的整数 $m$ , 满足 $\operatorname{conn}(\operatorname{conn}(s_2, n_2), m)$ 能由 $\operatorname{conn}(s_1, n_1)$ 生成。

$s_1$ 和 $s_2$ 长度不超过 100, $n_1$ 和 $n_2$ 不大于 $10^6$ 。

首先， $\operatorname{conn}(\operatorname{conn}(s_2, n_2), m) = \operatorname{conn}(s_2, n_2 * m)$ 。我们可以求出一个最大的整数 $m'$ ，满足 $\operatorname{conn}(s_2, m')$ 能由 $\operatorname{conn}(s_1, n_1)$ 生成。之后我们求出满足 $n_2 * m \leq m'$ 的最大整数 $m$ ，即为本题的答案。

$m^{\prime}$ 可能很大，其上界为 $|s_1|*n_1 / |s_2|$ 。为了提高效率，可以用二进制拆分思想，若 $m^{\prime} = 2^{p_{t - 1}} + \dots +2^{p_1} + 2^{p_0}$ ，则把 $\mathrm{conn}(s_2,m')$ 看作由 $\mathrm{conn}(s_2,2^{p_{t - 1}}),\mathrm{conn}(s_2,$ $2^{p_{t - 2}}),\dots ,\mathrm{conn}(s_2,2^{p_0})$ 这 $t$ 个字符串首尾连接形成。

注意到这 $t$ 个字符串都是由2的整数次幂个 $s_2$ 构成的。我们可以换一种思路，对于每个 $k \in [0, \log_2(|s_1| * n_1 / |s_2|)]$ ，求出从 $\operatorname{conn}(s_1, n_1)$ 的每个位置开始，至少需要多少个字符，才能生成 $\operatorname{conn}(s_2, 2^k)$ 。最后在总字符数不超过 $|s_1| * n_1$ 的前提下，用这些2的整数次幂拼成尽量大的 $m'$ 。

还有一个问题是 $n_1$ 的范围也非常大。不过， $\operatorname{conn}(s_1, n_1)$ 是 $s_1$ 重复 $n_1$ 次形成的。因此，只要没有到达结尾，从 $s_1[i]$ 开始往后的字符与从 $s_1[i + k * n_1]$ 开始往后的字符是相同的。我们不妨先假设 $n_1$ 足够大，即在 $s_1$ 重复无限次得到的字符串中执行计算。

综合上面的讨论，我们设 $F[i,j]$ 表示从 $s_1[i]$ 开始，至少需要多少个字符，才能生成 $\mathrm{conn}(s_2,2^j)$ 。状态转移方程为：

其含义是，在 $s_1$ 无限重复的字符串中，从 $s_1[i]$ 开始，先用尽量少的字符生成目标串的前半部分，紧接着在后边再用尽量少的字符生成目标串的后半部分。第二维 $j$ 是DP的“阶段”，第一维 $i$ 是附加状态。复杂度为 $O(|s_1|*\log (|s_1|*n_1 / |s_2|))$ 。

DP 的初值 $F[i,0]$ 就是从 $s_1[i]$ 开始生成 $s_2$ 需要的最少字符数。 $s_1$ 和 $s_2$ 都很

短，可以采用朴素算法直接计算。

在整个动态规划过程完成后，我们对DP得到的状态进行拼接。

1.枚举 $start = 0\sim |s_1| - 1$ ，作为 $\mathrm{conn}(s_1,n_1)$ 生成 $\mathrm{conn}(s_2,m')$ 的起始位置。
2. 初始化 $x = \text{start}, \text{ans} = 0$ ，然后从 $\log(|s_1| * n_1 / |s_2|)$ 到0倒序循环 $k$ 。
3. 如果 $x + F[x \bmod |s_1|, k] \leq |s_1| * n_1$ ，则令 $x = x + F[x \bmod |s_1|, k]$ ， $ans = ans + 2^k$ 。
4. ans 即为以 start 为起始生成位置时， $m'$ 的最大值。

string s1, s2;
int n1, n2;
long long f[105][32];
int main() {
cin >> s1 >> n1 >> s2 >> n2;
for (int i = 0; i < s1.size(); i++) {
    int pos = i;
    f[i][0] = 0;
    for (int j = 0; j < s2.size(); j++) {
        int cnt = 0;
        while (s1[pos] != s2[j]) {
            pos = (pos + 1) % s1.size();
            if (++cnt >= s1.size()) {
                cout << 0 << endl;
                return 0;
            }
        }
    pos = (pos + 1) % s1.size();
    f[i][0] += cnt + 1;
}

$\begin{array}{l}\mathrm{x + = f[x\%s1.size()][k];}\\ \mathrm{ans + = 1 <   <   k;}\\ \end{array}$    
}   
}   
m=max(m, ans);   
}   
cout<<m/n2<<endl;

对这两道题目进行总结，我们可以发现，用倍增优化的动态规划算法求解问题时，一般分为两部分。第一部分是预处理，用“阶段”成倍增长的DP，计算出若干与2的整数次幂相关的代表状态。第二部分是拼凑，基于“二进制划分”思想，用上一步得到的代表状态组合成最终的答案。