DP 学习笔记

· · 算法·理论

决策单调性 DP

对于某些 dp 会存在以下形式：f_i=\min (g_j+w(j,i))。设 i 的最优决策点是 d_i。

这种 dp 经常会存在决策单调性（可以证明或打表验证）。也就是说，对于 i<j，有 d_i\le d_j。

那么就可以分治处理：设 \text{solve}(L,R,dL,dR) 表示 L\sim R 的最优决策点都在 dL\sim dR 的处理过程。设 mid=(L+R)/2，先暴力求出 mid 的最优决策点 d。然后再调用 \text{solve}(L,mid-1,dL,d) 和 \text{solve}(mid+1,R,d,dR)，就可以分治处理了。时间复杂度为 O(n\log n)。

斜率优化 DP

link

对于两个决策点 a,b(a<b)，不妨设 a 比 b 更优，如果推出 {Y(a)-Y(b)\over X(a)-X(b)}\ge k 的形式（X 要保证单调递增，且 X,Y 与 i 无关，k 与 i 有关），那么就可以按照 X,Y 建系，若两点斜率 \ge k 则 a 更优，否则 b 更优。那么就可以维护一个凸包，并二分找出凸包上斜率与 k 最接近的地方，就是最优决策点。

若满足决策单调性（或 k 单调递增），那么可以弹出队首斜率小于 k 的点，此时队首即为最优决策点。

二分队列

二分队列内每一个元素都代表一个决策，其中存储了决策位置与最优决策有效范围。其中最优决策有效范围满足单调队列的性质。可以通过二分找出两个决策的有效范围的临界点。

int get(int i,int j)
{
    int L=i+1,R=n;
    int k=n;
    while(L<=R)
    {
        int mid=(L+R)>>1;
        if(f[i]+W(i+1,mid)<f[j]+W(j+1,mid))
        {
            L=mid+1;
            k=mid;
        }
        else R=mid-1;
    }
    return k;
}
bool check(LL mid)
{
    head=1; tail=0;
    q[++tail]={0,n};
    for(int i=1;i<=n;i++)
    {
        while(head<tail && q[head].mr<i)head++;
        f[i]=f[q[head].p]+W(q[head].p+1,i)+mid;
        s[i]=s[q[head].p]+1;
        while(head<tail && get(q[tail].p,i)<=q[tail-1].mr)tail--;
        q[tail].mr=get(q[tail].p,i);
        q[++tail]={i,n};
    }
    return s[n]>=k;
}

wqs 二分

wqs 二分常用于求解恰好选择 k 个物品时的最优方案 f(k)。当 f(x) 具有凸性时，可以使用 wqs 二分求解。

不妨假设 f(x) 为下凸（不妨假设不存在三点共线），现在想要求出它 f(k) 的值。

可以试图给函数加权，即每选择一个物品必须将价值 -d。这个操作相当于是用一条斜率为 d 的直线去切函数 f(x)，找到斜率最接近 d 的 x。再将 x 与目标 k 进行比较，对斜率进行二分直到找到目标 k 的位置。

三点共线

但是，可能出现三点共线的情况。面对这种情况，可以在 dp 时强迫选择最左边（或最右边）的点，便于更新答案。

L=-inf; R=inf;
while(L<=R)
{
    mid=(L+R)>>1;
    check(mid);
    //这里的 check 会更新 ans 和 cnt，
    //使得 ans 最小的情况下 cnt 最小。
    if(cnt<=k)
    {
        L=mid+1;
        res=ans+mid*k;
        //找到斜率最接近的位置更新
    }
    else R=mid-1;
}

值得注意的是，wqs 二分的斜率一定是整数，因为定义域连续、值域为整数。

选择至多 k 个

那么，怎么处理至多（或至少）选择 k 个的问题呢？

不妨先不加权求一遍答案，这时最优解为 f(x)。如果 x\le k，就代表全局最优解就在 x，直接输出答案即可；否则，因为函数凸性，答案一定为 f(k)，用 wqs 二分求解即可。

P2619

直接对白边加权，用 wqs 二分去跑 Kruskal 算法即可。

CF739E

一个质朴的 dp 是 f_{i,a,b} 表示考虑完前 i 个精灵后，两种精灵球各使用 a、b 个时的最大期望。

但是，这样做是 O(n^3) 的，考虑用 wqs 二分优化。去除选 b 个的那一维，设 f_{i,a} 表示考虑完前 i 个精灵后，第一种精灵球已使用 a 个，在每个 b 精灵球都有 d 的代价的情况下，的最大期望。同时记录最优解的情况下第二种精灵球选择了几个。

于是可以根据第二种精灵球的选择个数，来调节 d 的值。总时间复杂度 O(n^2\log V)。

这题甚至有更优做法。用 wqs 二分套 wqs 二分，设 f_i 表示当两种球代价分别为 d_1、d_2 时，的最大期望。两个维度均具有凸性，根据两种球选取的个数进行调节即可（注意处理三点共线的情况）。时间复杂度 O(n\log^2 V)。

Slope Trick

有时候，dp 的某个维度会特别大，但是 dp 数组可以画成一条凸的折线，那么就可以使用 slope trick 维护。通常，可以使用一些数据结构来维护斜率的变化点。

P4597

不妨设：

那么，就可以写出转移方程：

f_{u,x}=g_{u-1,x}+|x-{a_u}| g_{u,x}=\min\limits_{y\le x} f_{u,y}

固定 u，就可以按照 x 和 f_{u,x}（或 g _{u,x}）两个维度画出一条折线。因为 f 是若干个绝对值的相加，所以 f 一定是下凸的。

先考虑 g_{u-1,x}+|x-{a_u}| 的意义，这相当于将原折线叠加一个 V 形的折线；再考虑取 \min 的意义，这相当于将折线末端斜率 >0 的部分推平。

用一个大根堆维护所有斜率变化点。如果大根堆中有一个 x，则代表 x 处斜率变化了 1。那么两种操作就具有了意义：

  1. 叠加绝对值：向大根堆中加入两个 a_u。
  2. 推平斜率 >0 部分：删除大根堆中的最大元素。（不妨设它是 s）

但是，只维护斜率变化点还不够，我们还需要关心折线的最低点。容易发现只有叠加 |x-{a_u}| 的操作会使折线向上移动。容易发现 s 既是原折线的一个最低点，又是新折线的一个最低点。因此叠加绝对值会使折线最低点向上移动 s-a_u。

动态维护这个过程，最终折线最低点的纵坐标就是答案。

但是，如果要求出具体解怎么办？

不妨设 n 次在大根堆中删除的数依次为 s_1\sim s_n。则显然一定存在取 a_n=s_n 的最优解。

从 n 到 1 重复这个过程，就可以得到一组最优解。

P3642

设 f_{u,x} 表示将子树 u 的引爆时间（包括 u 连向它父亲节点的引线）调节至 x 的最小代价。

还是使用大根堆维护斜率变化点。先不考虑 u 连向它父亲节点的引线，则将它儿子节点的大根堆全部合并即可（即把折线暴力叠加）。

再考虑连向父亲节点的引线。不妨设它的长度为 t。首先，将这条折线向右平移 t 格，就能得到不改变该引线长度的 f 折线。

然后考虑改变这条引线的长度。分两种情况讨论：

  1. 缩短引线长度：将这条折线沿左上方移动 t 格（这里指沿 x 方向的投影），会扫过一片区域。
  2. 延长引线长度：将这条折线沿右上方无限平移，会扫过一片区域。

容易发现扫过区域并集的轮廓就是新的折线。

这会对大根堆产生什么影响呢？对于第一种操作，-1\to 0 及其右边的转折点会向右平移 t 格；对于第二种操作 +1\to +2 及其右边的转折点会消失。容易发现每次折线末端的斜率都是 +1。

转折点就可以维护了，那斜率最低点怎么维护？可以维护每条折线的最低点，再进行合并，但是比较麻烦。有一种更好的方法：注意到 f_{u,0} 的值一定是边权和。因此直接按照折点倒推最低点坐标即可。

P13954

维护凸包不一定要维护转折点坐标，有时候可以维护每个线段的斜率。这样的好处是非常好维护不同凸包的合并。

定义 f_{u,x} 表示将 u 子树内改为经过 x 个黑点的最小代价。用堆维护折线不同线段的斜率，即 f_{u,x}-f_{u,x-1}。那么合并就是暴力将堆对应位置的斜率相加。

另外，如果 u 所有子树都已经合并，那么 u 是黑点就要在堆中再加入一个 -1，如果是红点就再加入一个 +1。（因为相当于斜向平移后取 \min）

注意到最终答案是 f_{u,0} 与堆中所有负数斜率之和。在合并时维护负斜率之和即可。