DP 优化技巧学习

· · 个人记录

倍增优化 DP

例题 P1081 [NOIP2012 提高组] 开车旅行

需要满足任意划分性，对“阶段”这一维度用倍增，并且只保留 2 的整数次幂阶段。这是第一部分“预处理”。然后是第二部分“拼凑”答案。

数据结构优化 DP

例题 UVA12983 The Battle of Chibi

不同于上面倍增对阶段的优化的是，数据结构优化 DP 针对的是决策，优化的是转移过程。数据结构维护的是决策集合，需要关注上下界的变化。

总之我们需要尽量分离 DP 决策的限制条件。内层循环时把外层变量看作定值。简单的限制条件用循环顺序处理，复杂的条件用数据结构维护，注意配合。

有时会出现数据结构的嵌套，建立映射关系等等。

单调队列优化 DP

例题 AcWing 298. 围栏

数据结构优化 DP 的一种，由于常用于优化一类问题所以单独拿出来写一下。

单调队列非常适合优化决策的取值上下界均单调变化，每个决策在候选集合中插入或删除至多一次的问题。

“如果一个选手比你小又比你强，你就打不过他了。”也称“你被单调队列了。”单调队列优化有点像搜索中的最优化剪枝，及时排除了不优的答案，从而高效转移。

大致的流程基本都如下：

  1. 检查队头合法性，排除过时决策；
  2. 取队头为最优决策转移；
  3. 插入新决策，入队前检查队尾单调性，排除无用决策。

只关注“状态变量”“决策变量”及其所在维度，状态转移方程大都可以归为如下形式：

F[i]=\min_{L(i)\leq j\leq R(i)} \left\{F[j]+val(i,j)\right\}

上式所代表的问题覆盖范围广泛，是 DP 中一类非常基本、非常重要的模型，也被称为 1D/1D 的动态规划。它是个最优化问题。其中一次函数 L(i) 、 R(i) 限制了决策 j 的取值范围，并保证其上下界变化单调。 val(i,j) 是一个关于变量 i、j 的多项式函数，通常是决定使用何种优化策略的关键。使用单调队列优化的基本条件就是多项式 val(i,j) 的每一项仅与 i 或 j 有关。具体地，我们将 val(i,j) 分成两部分，第一部分仅与 i 有关，第二部分仅与 j 有关，在单调队列中维护第二部分的单调性，及时排除不可能成为最优解的决策，从而达到优化 DP 的目的。

斜率优化 DP

例题 P5785 [SDOI2012]任务安排

单调队列优化需要满足多项式 val(i,j) 的每一项仅与 i 或 j 有关，斜率优化用于多项式 val(i,j) 中包含 i,j 的乘积项的优化。

得到状态转移方程之后，我们把取最值的函数撇开，把外层变量 i 当作定值，对方程进行移项。左边放和决策变量 k 有关的值，右边放 j,k 乘积项和仅与 j 有关的项，以与 j 相关的值作为乘积项的斜率，将整个方程视为一条在关于 k 的平面直角坐标系中的直线。当截距最小时 f 最小。

对于一个决策 k ，我们将其放在平面直角坐标系中作为一个点。直线过某个点时有意义。为了快速转移，我们维护凸壳，建立单调队列。队头和直线的斜率比，队尾和 i 比。

除法变成乘法避免精度问题，感觉还是很套路的，有了状态转移方程面包也有了牛奶也有了。

这就是为什么说状态转移方程是 DP 的核心的原因。

四边形不等式优化 DP

设 w(x,y) 是定义在整数集合上的二元函数。若对于定义域上的任何整数 a\leq b\leq c\leq d ，都有 w(a,d)+w(b,c)\geq w(a,c)+w(b,d) 成立，则称函数 w 满足四边形不等式。

定理（另一种定义）：设 w(x,y) 是定义在整数集合上的二元函数。若对于定义域上的任何整数 a < b ，都有 w(a,b+1)+w(a+1,b)\geq w(a,b)+w(a+1,b+1) 成立，则函数 w 满足四边形不等式。

1D/1D 类型

例题 P1912 [NOI2009] 诗人小G

考虑代价函数是否满足四边形不等式，即区间和小于等于嵌套和。

在 1D/1D 状态转移方程中，若代价函数 val(j,i) 满足四边形不等式，则决策具有单调性，考虑单调队列维护三元组，在队列中二分。

具体地，先看队头的 r ，如果等于 i-1 ，删了。否则让队头的 l=i 。然后用队头存的 j 更新答案。接着尝试插入新决策 i 。

  1. 如果对于队尾的 l ，队尾的 j 比 i 差，则一直删除队尾。
  2. 如果对于队尾的 r ，队尾的 j 比 i 优，则插入 (i,pos,N) 。
  3. 否则在区间上二分，完了断开，插入 (i,pos,N) 。

2D/1D 类型

例题 AcWing 2889. 再探石子合并

定理:在状态转移方程 F_{i,j}=\min_{i\leq k < j}\left\{F_{i,k}+F _{k+1,j}+w(i,j)\right\} 中（特别地， F_{i,i}=w(i,i)=0）,若有

  2. 对于任意 a\leq b\leq c\leq d ，有 w(a,d)\geq w(b,c) 。

那么 F 也满足四边形不等式。

定理：在状态转移方程 F_{i,j}=\min_{i\leq k < j}\left\{F_{i,k}+F _{k+1,j}+w(i,j)\right\} 中（特别地， F_{i,i}=w(i,i)=0）,记 P_{i,j} 为令 F_{i,j} 取得最小值的 k 值，若 F 满足四边形不等式，那么对于任意 i < j ,有 P_{i,j-1}\leq P_{i,j}\leq P_{i+1,j} 。即缩小了 P_{i,j} 的上下界。转移均摊 O(1) ，算法复杂度由 O(n^3) 优化到了 O(n^2) 。

告一段落，以后要多加练习，先去补其他知识点。

参考文献：lyd蓝书