DP优化

一些关于DP的小优化：

前缀和优化（用于 \(dp[i]=dp[i-k]+v[i]\)的转移）

bitset优化（01背包（价值能否取到），常数为 \(\omega=1/32\)）

单调队列优化（求恒长区间最大/小值）

二进制优化（完全背包问题，\(O(n^2\ logn)\) ）：P1776

线段树优化：CF1557D

斜率优化：见下文

四边形不等式：见下文

树链剖分（DDP）

斜率优化

本蒟蒻终于被迫学习斜率优化了

这类问题的优化的转移方程是：\(b(i)=max/min\{y(j)-k(i)\times x(j)\},j < i\)

以本题为例：

一个朴素的转移方程：

\[dp[i]=min(dp[j]+(i-j-1+sum[i]-sum[j]-L)^2) \]

其中，\(sum[i] = \sum_{k=1}^jc[k]\)

再合并，令 \(pre[i]=sum[i]+i\)

得：

\[dp[i]=min(dp[j]+(pre[i]-pre[j]-(L+1))^2) \]

强拆！

\[dp[i]=min(dp[j]+(pre[i]-(L+1))^2-2(pre[i]-(L+1))\times pre[j]+pre[j]^2) \]

移项：

\[dp[i]-(pre[i]-(L+1))^2=min(dp[j]-2(pre[i]-(L+1))\times pre[j]+pre[j]^2) \]

\[\begin{aligned} b_i&=dp[i]-(pre[i]-(L+1))^2,\\ x_j&=pre[j],\\ y_j&=dp[j]+pre[j]^2,\\ k_i&=2(pre[i]-(L+1))\\ \end{aligned}\]

那就变成了 \(y = kx+b\) 的转换式 \(b = y - kb\)

我们要最小化 \(b\) ，就是最小化直线的截距

我们可以将 \((x_j,y_j)\) 看作平面上的点，现在有一条斜率为 \(k_i\) 的直线，从下往上移动，碰到的第一个点就是我们的转移决策点（因为要最小化 \(b_i\)）

实际上，我们只需要维护下凸壳的那些点，而对于本题，显然 \(k_i\) 随 \(i\) 的增大而增大，所以我们只需要用一个单调队列来维护凸壳上的点

借用 OI-Wiki 中的图：

我们令 \(K(q_{e-1},q_e)\) 为 \((x_{q_{e-1}},y_{q_{e-1}})\) 与 \((x_{q_{e}},y_{q_{e}})\) 两点连线的斜率

显然，我们要找的决策点就是凸壳中满足 \(K(q_{e-1},q_e)\le k_i < K(q_e,q_{e+1})\) 的点 \(e\)

因为 \(k_i\) 是递增的，所以下一次 DP 只需要从 \(e\) 开始找决策点，这样均摊下来就是 \(O(1)\) 的

又因为 \(x_i=pre[i]\) 是递增的，所以点 \(i\) 一定会加入到凸壳中，我们只需要将 \(K(q_{e-1},q_e)<=K(q_e,(x_i,y_i))\) 的点弹出，再将 \(i\) 加入到队列即可

注意：队列的初始状态应该是有一个点 (0,0) ，否则 \(c_1\) 将永远无法和后面的玩具合并，导致错误！

一般化

但如果我们将上述题目的条件改改，使得 \(c_i\) 可以为负，那么这时候 \(k_i\) 和 \(x_i\) 就不单调递增了，是不是就做不了了？？？

当然不是啊，不然我提出这个问题干嘛

对于 \(k_i\) （斜率）不单调的话，我们直接在凸壳上二分，还是找满足原来那个条件的点即可

但如果 \(x_i\) 不是单调的，我们就很难去更新凸壳了

一种方法就是用平衡树维护凸包，就是找到 \(x_j \le x_i \le x_{j+1}\) 的地方，根据凸包的性质不断向两边删点（或者自己本来就在凸包里面就不用管了）

但用平衡树十分滴复杂，有没有更好写的算法？（其实用 set 是可以实现的）

有！就是我们万能的 CDQ分治

我们假定分治到 \((l,r)\)，且 \((l,mid)\) 已经处理完了，现在要对 \((mid+1,r)\) 进行贡献

注意：这时候 \((mid+1,r)\) 还没有分治下去！

我们先将 \((l,mid)\) 的点以 \(x\) 为第一关键字， \(y\) 为第二关键字排序，然后就直接求一遍凸壳

然后我们再将 \((mid+1,r)\) 按照斜率 \(k\) 将编号从小到大排序

这时候我们就可以正常像上面用单调队列跑 DP 了

转移完后，显然 \((l,mid)\) 的决策点已经没有用处了，我们可以直接将其舍弃掉，转到 \((mid+1,r)\) 的分治

整个分治的时间复杂度是 \(O(nlog^2n)\) 的。

当然，我们也可以用 李超线段树 直接跑 DP ，就是将上面的 \(k,x,y,b\) 稍微换一下，每次 DP 在树上查询最大/小值，求完后再更新线段树即可

dp 套 dp

适用范围：要求你构造一些满足特殊要求的序列或字符串，并统计出有多少种不同的方案数

也就是说，这是一种计数DP的 trick

我们用这道例题讲解一下

我们先考虑求两个序列的 LCS 的方式：

\[dp_{i,j}=max(dp_{i-1,j},dp_{i,j-1},dp_{i-1,j-1}+[a_i=b_j]) \]

其中，\(dp_{i,j}\) 表示 \(a\) 串的前 \(i\) 位与 \(b\) 串的前 \(j\) 位的 LCS

显然，一种 \(dp_i\) 对应着一类的 \(a\) 串

而题目又是要我们构造 \(a\) 串，我们就考虑记录下每种 \(a\) 串的结果 \(dp_i\)，并以此为外层 DP 的状态进行转移

我们就定义 \(DP_{i,j}\) 表示：当 \(a\) 串长度为 \(i\) 时，它的 \(dp_i\) 结果为 \(j\) 的方案数

但难不成我们要将所有的 \(dp_i\) 都记录下来，然后再一个个跑吗？

诶，我们这时候就要注意到 \(k\) 的大小了，它才 \(15\) 啊

是不是又一种直觉，我们可以用状压来记录 \(dp_i\) ？

事实确实如此！因为我们注意到，\(dp_{i,j}-dp_{i,j-1}\) 要不为 0 ，要不为 1

那我们就考虑将 \(dp_i\) 进行差分后，再用状压记录状态

那我们每次 DP 加入一个新的字符时，就枚举上一个字符的所有状态，解压后再求新的状态，进行转移

题目还有一个不能出现 NOI 串的限制，那我们只需要每次都记录最后几位是否为 N、NO 或没有即可

四边形不等式

（学完斜率优化才来学决策单调性的屑）

2D1D 区间转移类

在许多的区间DP中（如石子合并），我们有如下的状态转移方程：

\[f_{l,r}=min\{f_{l,k}+f_{k+1,r}\}+w_{l,r} \]

这显然是 \(O(n^3)\) 的，但当 \(n>1e4\) 时，我们就寄了

但 \(w_{l,r}\) 满足一些特殊性质，让我们可以对它进行优化：

  • 区间包含单调性

当 \(l\le l'\le r'\le r\) 时，有 \(w_{l',r'} \le w_{l,r}\) 成立，则函数 \(w\) 对于区间包含具有单调性

  • 四边形不等式

当 \(l_1\le l_2\le r_1\le r_2\) 时，有 \(w_{l_1,r_1}+w_{l_2,r_2}\le w_{l_1,r_2}+w_{l_2,r_1}\) 成立，则称函数 \(w\) 满足四边形不等式（简记为“交叉小于包含”）

但我们需要的是 \(f_{l,r}\) 满足四边形不等式，才能进行优化

  • 引理：

若 \(w_{l,r}\) 满足上面的两个性质，则 \(f_{l,r}\) 也满足四边形不等式

令 \(u\) 为 \(f_{l_1,r_2}\) 的最优决策点，\(v\) 为 \(f_{l_2,r_1}\) 的最优决策点

（由于当 \(l_2=r_1\) 时 \(v\) 是没有意义的，所以我们需要分开讨论）

显然，当 \(l_1=l_2\) 或 \(r_1=r_2\) 时，不等式相等，成立

下面我们用归纳法证明区间长度为 \(r_2-l_1\) 满足四边形不等式

  1. 当 \(l_1 时

    A. 若 \(u < r_1\)，有 \(f_{l_1,r_1}\le f_{l_1,u}+f_{u+1, r_1}+w_{l_1,r_1}\)，由归纳法得 \(f_{u+1,r_1}+f_{l_2,r_2}\le f_{u+1,r_2}+f_{l_2,r_1}\)，两式相加，有：

    \[f_{l_1,r_1}+f_{l_2,r_2}\le f_{l_1,u}+f_{u+1,r_2}+f_{l_2,r_1}+w_{l_1,r_1} \]

    又因为 \(w_{l_1,r_1}\le w_{l1,r2}\)，\(f_{l_1,r_2}= f_{l_1,u}+f_{u+1, r_2}+w_{l_1,r_2}\)

    所以 \(f_{l_1,r_1}+f_{l_2,r_2}\le f_{l_1,r_2}+f_{l_2,r_1}\)

    B. 若 \(u\ge r_1\)，有 \(f_{l_2,r_2}\le f_{l_2,u}+f_{u+1, r_2}+w_{l_2,r_2}\)，由归纳法得 \(f_{l_1,r_1}+f_{l_2,u}\le f_{l_1,u}+f_{l_2,r_1}\)，两式相加，有：

    \[f_{l_1,r_1}+f_{l_2,r_2}\le f_{l_1,u}+f_{u+1,r_2}+f_{l_2,r_1}+w_{l_2,r_2} \]

    又因为 \(w_{l_2,r_2}\le w_{l1,r2}\)，\(f_{l_1,r_2}= f_{l_1,u}+f_{u+1, r_2}+w_{l_1,r_2}\)

    所以 \(f_{l_1,r_1}+f_{l_2,r_2}\le f_{l_1,r_2}+f_{l_2,r_1}\)

  2. 当 \(l_1 时

    A. 若 \(u\le v\)，则 \(l_1\le u < r_1\), \(l_2\le v，有

    \[\begin{aligned} f_{l_1,r_1}\le f_{l_1,u}+f_{u+1,r_1}+w_{l_1,r_1}\\ f_{l_2,r_2}\le f_{l_2,v}+f_{v+1,r_2}+w_{l_2,r_2} \end{aligned}\]

    由 \(u+1\le v+1\le r_1 and 归纳法，有 \(f_{u+1,r_1}+f_{v+1,r_2}\le f_{u+1,r_2}+f_{v+1,r_1}\)，前两个不等式相加，将第三个不等式代入，得

    \[f_{l_1,r_1}+f_{l_2,r_2}\le f_{l_1,u}+f_{l_2,v}+f_{u+1,r_1}+f_{v+1,r_2}+w_{l_1,r_1}+w_{l_2,r_2}\le f_{l_1,r_2}+f_{l_2,r_1} \]

    B. 若 \(u>v\)，则 \(l_2\le u < r_2\), \(l_1(l_2)\le v，有

    \[\begin{aligned} f_{l_2,r_2}\le f_{l_2,u}+f_{u+1,r_2}+w_{l_2,r_2}\\ f_{l_1,r_1}\le f_{l_1,v}+f_{v+1,r_1}+w_{l_1,r_1} \end{aligned}\]

    由\(l_1 and 归纳法，有 \(f_{l_1,v}+f_{l_2,u}\le f_{l_1,u}+f_{l_2,v}\)，前两个不等式相加，将第三个不等式代入，得

    \[f_{l_1,r_1}+f_{l_2,r_2}\le f_{l_1,v}+f_{l_2,u}+f_{v+1,r_1}+f_{u+1,r_2}+w_{l_1,r_1}+w_{l_2,r_2}\le f_{l_1,r_2}+f_{l_2,r_1} \]

综上所述，\(f_{l_1,r_1}+f_{l_2,r_2}\le f_{l_1,r_2}+f_{l_2,r_1}\)

  • 定理：

记 \(t_{l,r}\) 为 \(f_{l,r}\) 的最优决策点，则有：

\[t_{l,r-1}\le t_{l,r}\le t_{l+1,r} \]

证明：设 \(L = t_{l,r-1}, M = t_{l,r}, R = t_{l+1, r}\)

  1. 若 \(L>M\)

    根据 \(M+1, 有 \(f_{M+1, r-1}+f_{L+1,r}\le f_{M+1,r}+f_{L+1,r-1}\)

    又根据 \(L\) 为 \(f_{l,r-1}\) 的最优决策点，得 \(f_{l,L}+f_{L+1,r-1}\le f_{l,M}+f_{M+1,r-1}\)

    两式相加，得 \(f_{l,L}+f_{L+1,r}\le f_{l,M}+f_{M+1,r}\)

    这说明 \(L\) 比 \(M\) 对于 \(f_{l,r}\) 更优，显然矛盾，所以 \(L\le M\)

  2. 若 \(M>R\)

    根据 \(l, 有 \(f_{l, R}+f_{l+1,M}\le f_{l,M}+f_{l+1,R}\)

    又根据 \(R\) 为 \(f_{l+1,r}\) 的最优决策点，得 \(f_{l+1,R}+f_{R+1,r}\le f_{l+1,M}+f_{M+1,r}\)

    两式相加，得 \(f_{l,R}+f_{R+1,r}\le f_{l,M}+f_{M+1,r}\)

    这说明 \(R\) 比 \(M\) 对于 \(f_{l,r}\) 更优，显然矛盾，所以 \(M\le R\)

通过上述的证明，我们在DP的过程中就可以减少枚举决策点的次数，复杂度能够优化到：

\[\sum_{1\le l

  • 另一种转移形式

\[f_{l,r}=min\{f_{l-1,k}\}+w_{k,r} \]

其中 \(1\le l\le n,\ 1\le j\le m\)，所以直接做的复杂度是 \(O(nm^2)\) 的

但实际上，如果 \(w_{l,r}\) 能满足区间包含单调性和四边形不等式，\(f_{l,r}\) 也一样满足四边形不等式，有 \(t_{l,r-1}\le t_{l,r}\le t_{l+1,r}\)

由于是逐层转移，我们考虑对第 \(i\) 层进行分治

我们设置状态 \((l,r,t_l,t_r)\)，表示分治到 \([l,r]\)，\(f_{i,mid}\) 的最优决策点在 \([t_l, t_r]\)

我们暴力枚举 \(f_{i,mid}\) 的决策点，找到最优的决策点 \(t_{mid}\)，再向下分治 \((l,mid,t_l,t_{mid}),\ (mid+1, r, t_{mid},t_r)\)

时间复杂度就优化到 \(O(nm\ log\ m)\)

1D1D 转移类

\[f_r=min\{f_l+w_{l,r}\} \]

如果 \(w_{l,r}\) 满足四边形不等式，令 \(t_r\) 为 \(f_r\) 的最优决策点，则有 \(r_1

证明：令 \(L=t_{r_1},\ R=t_{r_2}\)

  • 若 \(L>R\) ，则 \(R，由四边形不等式有 \(w_{R,r_1}+w_{L,r_2}\le w_{R,r_2}+w_{L,r_1}\)

  • 因为 \(L\) 是最优决策点，所以有 \(f_L+w_{L,r_1}\le f_R+w_{R,r_1}\)

  • 两不等式相加，得 \(f_L+w_{L,r_2}\le f_R+w_{R,r_2}\)

  • 这显然与 \(R\) 是 \(f_{r_2}\) 的最优决策点相矛盾，所以 \(L\le R\)

但这时我们仅仅确定了下界，最坏情况下仍是 \(O(n^2)\) 的

我们考虑使用单调队列，里面记录的是决策点，每个决策点能够转移到的区间为 $[L_{q[i]},L_{q[i+1]}-1] $

当我们要转移到 \(f_i\) 时，我们就取出队头，如果他的转移区间 \([L_{q[he]},L_{q_[he+1]}-1]\) 不包含 \(i\)，也就是 \(L_{q[he+1]}\le i\)，我们就将其弹出，最后没被弹出的队头就是最优决策点

那我们如何更新队列呢？我们就每次取出队尾，比较一下从 \(i\) 转移到 \(L_{q[ta]}\) 是否比从 \(q_{ta}\) 转移到 \(L_{q[ta]}\) 更优，如果是，代表 \(i\) 所能转移到的区间已经覆盖了 \(t_{ta}\) 了，根据决策单调性，我们就将队尾弹出

但这还没完，因为 \(i\) 虽然没有覆盖某个队尾，但它可能覆盖了其中一小部分，因此我们要对队尾所覆盖的区间 \([L_{q[ta]},N]\) 进行二分，找出第一个点 \(k\)，使得 \(i\) 转移到 \(k\) 比 \(L_{q[ta]}\) 转移到 \(k\) 更优，作为 \(i\) 覆盖区间的起点

时间复杂度则为 \(O(n\ log\ n)\)

快速判断

对于1D1D：详见大佬

简而言之，对于每个决策函数 \(f_j(i)\)（也就是转移中只和 \(j\) 有关的变量），如果任意两个函数只有一个交点：直线或形状相同（可以通过平移转换），其导函数单调，就有可能是决策单调

对于2D1D：证明 \(w_{l,r+1}+w_{l+1,r}\le w_{l,r}+w_{l+1.r+1}\)，也就是证明 \(w_{l,r}\) 满足四边形不等式，那么 \(f_{l,r}\) 也一般会满足四边形不等式（毕竟没人出个决策单调的诈骗题吧......）

优化杂技

相关

标签