前言
这部分主要讲一讲 DP 优化的一些方法，显然我的实力不太够，所以只能写一些比较简单的东西。
如动态规划（Ⅰ）中提到的，动态规划的优化一般就可以从两个方面入手：一个是状态表示、另一个是决策集合，也就是状态转移的角度来优化。下文主要就是分别从这两个角度，阐述不同的 DP 优化方法。
倍增优化 DP
倍增优化 DP，是从状态表示的方面来进行 DP 优化。简单来说，因为动态规划经常采用按阶段的递推形式实现，所以也可以按照类似的方法，使用倍增把阶段的线性增长优化为成倍增长，也就是把一段 \(\mathcal O(n)\) 的部分优化成 \(\mathcal O(\log n)\)，显然，优化效果显著。
下面给一道例题来讲一下倍增优化 DP 的方式。
例题
题面太长了就不放了。
这道题 \(70\) 分代码是比较好写的，建议先写一下 \(70\) 分的 \(\mathcal O(n^2)\) 做法：
维护四个数组 \(city_1[i],city_2[i],dis_1[i],dis_2[i]\)，分别表示距离城市 \(i\) 最近的城市，次近的城市，以及它们分别到城市 \(i\) 的距离。我们朴素地暴力 \(\mathcal O(n^2)\) 便能解决这个问题。
然后对于两个问题，我们便运用这四个数组，\(O(nm)\) 的枚举即可，没啥难度。
code
然后我们考虑怎么优化，其实这个题我感觉不像是一个真正的 DP，因为你一旦确定了起点，其实你的路径就是固定的了，而正是因为这个性质，使得我们可以采用倍增的方法来优化我们的复杂度。
倍增优化 DP
想要倍增优化，我们就考虑我们想知道什么：行驶到了哪座城市、小 A 行驶的路程、小 B 行驶的路程。根据这个，我们设出倍增 DP 的数组：
下文中，\(k=0\) 代表小 A 开车，\(k=1\) 代表小 B 开车。
设 \(f_{i,j,k}\) 表示从城市 \(j\) 出发，行驶 \(2^i\) 天，\(k\) 先开车，最终会到达的城市；
设 \(da_{i,j,k}\) 表示从城市 \(j\) 出发，行驶 \(2^i\) 天，\(k\) 先开车，小 A 行驶的路程；
设 \(db_{i,j,k}\) 表示从城市 \(j\) 出发，行驶 \(2^i\) 天，\(k\) 先开车，小 B 行驶的路程。
假设我们已经知道了暴力解法中的四个数组的值，我们考虑怎么求倍增数组。
初值的设定：
f[0][i][0] = city2[i], f[0][i][1] = city1[i];
da[0][i][0] = dis2[i], da[0][i][1] = 0;
db[0][i][0] = 0 ,db[0][i][1] = dis1[i];
结合数组意义应该不难看懂，接下来，我们按照预处理倍增数组的一般思路，递增第一维。
需要注意的是，当 \(i=1\) 时，我们从 \(i=0\) 扩展而来，这时候司机是变了一个人的；而当 \(i>1\) 时，我们从 \(i-1\) 转移而来，这时第 \(2^i\) 天和 \(2^{i-1}\) 天都是偶数，是由同一个人转移而来，所以要分类讨论一下。
当 \(i=1\) 时：
f[1][j][k] = f[0][f[0][j][k]][k ^ 1];
da[1][j][k] = da[0][j][k] + da[0][f[0][j][k]][k ^ 1];
db[1][j][k] = db[0][j][k] + db[0][f[0][j][k]][k ^ 1];
当 \(i>1\) 时：
f[i][j][k] = f[i - 1][f[i - 1][j][k]][k];
da[i][j][k] = da[i - 1][j][k] + da[i - 1][f[i - 1][j][k]][k];
db[i][j][k] = db[i - 1][j][k] + db[i - 1][f[i - 1][j][k]][k];
求解问题
朴素的求解问题是一步一步模拟走过的城市。有了倍增数组后，我们自然就可以进行倍增跳步了。具体实现如下：
-
我们给定 \(pos=0,disA = 0 ,disB= 0\)，分别表示现在在哪个城市，小 A 的路程，小 B 的路程。
-
令 \(i\) 从 \(\log n\) 枚举到 \(0\)，判断 \(f_{i,pos,0}\) 是否越界，并且 \(disA + disB + da_{i,pos,0} + db_{i,pos,0} \leq x\) 是否成立。如果不越界且成立，那么就直接令 \(pos=f_{i,pos,0},disA += da_{i,pos,0},disB += db_{i,pos,0}\)，这也就实现了我们的跳步操作。
第二步结束后，\(disA\) 和 \(disB\) 就可以求出来了，有了这个，问题 \(1,2\) 就都很好解决了，我们就可以在 \(\mathcal O(n\log n)\) 的时间下解决问题。
dis = disA = disB = 0 , pos = i;
for(re int j=18;j>=0;j--)
{
if(f[j][pos][0] != n+1 && disA + disB + da[j][pos][0] + db[j][pos][0] <= x)
{
disA += da[j][pos][0];
disB += db[j][pos][0];
pos = f[j][pos][0];
}
}
解决根源的初始化
其实我们发现，我们还漏了一个地方，也就是那四个数组的初始化其实还是 \(\mathcal O(n^2)\) 的，但因为这个地方的优化跟倍增没有关系，所以放到最后来说。
具体来说，我们维护一个 multiset，存储节点编号和节点高度，初始时我们插入 \(4\) 个边界，两个 \(-\inf\)，两个 \(\inf\)，然后我们从右向左将每个城市插入进去，然后利用 multiset \(\mathcal O(\log n)\) 的查询它的前驱，前驱的前驱，后继，后继的后继，然后取一个最小值和次小值即可。（multiset 里面按高度从小到大排序）。
这样一来，初始化也是 \(\mathcal O(n\log n)\) 的了，综上，我们运用倍增优化 DP，就在 \(\mathcal O((n+m)\log n)\) 解决了这个问题。
此外的例题还有 AcWing294.计算重复，这里有两种倍增的手法，但其中一种更为优秀，具体可以看第一篇题解。
总结
倍增优化 DP 其实感觉不怎么像是 DP，因为能使用倍增 DP 的前提是，每个路线是已经确定的了，是静态的。当然这其中也有 DP 的思想，因为我们设的倍增数组其实就是 DP 的体现。