DP-优化

· · 个人记录

link to cnblog

一些关于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)

令

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 - kx

我们要最小化 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<l_2=r_1<r_2 时

    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<l_2<r_1<r_2 时

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

    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<r_2 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<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}\le f_{l_1,v}+f_{v+1,r_1}+w_{l_1,r_1} \end{aligned}

    由l_1<l_2\le v<u 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<L+1\le r-1<r, 有 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<l+1\le R<M, 有 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<r\le n}t_{r,i+1}-t_{r-1,i}=\sum_{i=1}^nt_{i,n}-t_{1,i}\le n^2 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\ n)

也就是当 w_{k,r} 不能在 O(1) 下计算

我们可以采用莫队双指针移动的方法

也就是在暴力求 mid 的决策点时，像莫队那样移动到需要的区间

这样一看，似乎复杂度假掉了

但实际上，这还是 O(nm\log n) 的

因为当我们枚举到 l,r,tl,tr 时，双指针一定在 tl,tr 内

因为右指针不动，只有左指针移动 O(mid-l) 次

递归到左儿子的时候暴力移动到 tl,tmid，给右儿子移动到 tmid,tr，这部分也不超过 r-l

因此平衡到与分治一样的复杂度

1D1D 转移类

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

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

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

但这时我们仅仅确定了下界，最坏情况下仍是 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：详见大佬FlashHu的博客

简而言之，对于每个决策函数 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} 也一般会满足四边形不等式（毕竟没人出个决策单调的诈骗题吧......）

SOS DP

问题引入：求

F[S]=\sum_{i\in S}A[i]

我们有 O(4^n) 的暴力，有 O(3^n) 的子集枚举，但一旦 n 较大，我们都得凉凉

其实我们有一个 O(n2^n) 的做法

我们令 dp[S][i]=\sum_{j\in S\ and\ j \oplus S < 2^{i+1}} A[j]

考虑如何转移

dp[S][i - 1]\ (S\ \&\ 2^i=0) \\ dp[S][i - 1] + dp[S \oplus 2^i][i - 1]\ (S\ \&\ 2^i=2^i) \end{matrix}\right.

最后我们输出 dp[S][n] 即可