「DP 浅析」斜率优化

发表于 更新于 分类于
斜率优化的简单讲解

#0.0 屑在前面

将结合经典例题 「HNOI2008」玩具装箱 以及 「NOI2007」货币兑换 进行讲解。

#1.0 简述

#1.1 适用情况

斜率优化一般适用于状态转移方程如下的 DP \[ f_i=\mathop{\min/\max}\limits_{0\leq j<i}\{a_i\cdot b_j + c_i + d_j\}, \] 其中 \(a_i,b_j,c_i, d_j\) 在计算 \(f_i\) 时都是常数（已知量）。

#1.2 大致思想

为了方便叙述，下文中的方程都采用 \(f_i=\min\limits_{0\leq j<i}\{a_i\cdot b_j + c_i + d_j\}\) 的形式。

假设我们从决策点 \(j\) 处转移到 \(i\)，那么应当有转移式 \[ f_i=a_i\cdot b_j+c_i+d_j, \] 此时，对于众多可能的决策点 \((b_j,d_j)\)，将上式化作一个直线斜截式方程，于是有 \[ d_j=-a_i\cdot b_j+f_i-c_i, \] > 换句话讲，其实这里的形式转换就是将只与 \(j\) 有关的项放到一边，剩下的放到另一边。

又因为 \(c_i\) 是一个已知的常数，于是我们的目的就变为了对于斜率 \(-a_i\)，在所有的决策点中，我们选择需要令直线的截距 \(f_i-c_i\) 尽可能小那一个。

此时，我们还不能仅利用上面的结论对 DP 的时间复杂度进行优化，我们还需要研究决策点的性质。首先，不难看出，仅有所有下凸包上的点是可能的决策点，如下图：

显然（相对较严谨的证明见 #1.3 关于决策一定在凸包上的证明）不在下凸包上的点，无论在哪种斜率下，在下凸包上都具有更好的替代品。

一个经典的结论是：对于指定斜率 \(k\) 的直线，与上/下凸包上相切确定的一条纵轴截距最大/最小。而由于下凸壳上的线段直线的斜率单调递增，于是一个点是切点当且仅当其左边的线段斜率 \(<k\) 而右边的 \(>k\)。

综上，我们在寻找最优决策点的时候就可以通过 \(O(n\log n)\) 维护整个下凸包，单次 \(O(\log n)\) 二分查询寻找最优决策点的位置，另一种写起来更加简洁的方式是采用 CDQ 分治。同时，如果决策点本身具有一定的特殊性质（如单调性），我们甚至可以不保存整个下凸包，对时间复杂度可能又有进一步的优化。这些在下文都会提到。

事实上，我们也可以用 李超线段树 维护斜率优化[7]。

#1.3 关于决策一定在凸包上的证明

这里状态转移方程依旧都采用 \(f_i=\min\limits_{0\leq j<i}\{a_i\cdot b_j + c_i + d_j\}\) 的形式。

设 \(0\leq j_1<j_2<i\) 为 \(i\) 的两个决策点，且满足决策点 \(j_2\) 优于 \(j_1\)，那么有 \[ a_i\cdot b_{j_1}+c_i+d_{j_1}\geq a_i\cdot b_{j_2}+c_i+d_{j_2}, \] 接下来的一步是进行参变分离，将含有 \(j\) 的项视为常数，将含有 \(i\) 的项视为变量（即使它本身应当是常数），然后进行移项，尝试用含 \(j\) 的项表示出含 \(i\) 的项。 \[ a_i\cdot b_{j_1}+c_i+d_{j_1}\geq a_i\cdot b_{j_2}+c_i+d_{j_2},\\ a_i\cdot (b_{j_2}-b_{j_1})\leq d_{j_1}-d_{j_2}, \]

那么此时对于 \(b_{j_1},b_{j_2}\) 的大小分类讨论（不考虑 \(b_{j_1}=b_{j_2}\) 的情况）有 \[ \begin{cases} -a_i\geq\dfrac{d_{j_2}-d_{j_1}}{b_{j_2}-b_{j_1}},\qquad b_{j_2}>b_{j_1},\\ -a_i\leq\dfrac{d_{j_2}-d_{j_1}}{b_{j_2}-b_{j_1}},\qquad b_{j_2}<b_{j_1},\\\tag1\label{tag1} \end{cases} \] 如果我们将决策点表示为 \((b_j,d_j)\)，那么此时不等号右边是斜率式的形式。

考虑位置关系如下的三个决策点：

设此时 \(A\) 与 \(B\) 两点之间的线段的斜率为 \(k_0\)，我们对 \(-a_i\) 进行分类讨论。

第一种情况是 \(k_0>-a_i\)，此时显然有 \(\overline {BC}\) 的斜率 \(k_1>k_0>-a_i\)，而根据 \(\eqref{tag1}\)，如果 \(C\) 比 \(B\) 更优，应当有 \(k_1\leq-a_i\)，矛盾，于是此时应当点 \(B\) 更优。

第二种情况是 \(-a_i>k_0\)，此时显然有 \(\overline{AC}\) 的斜率 \(k_2<k_0<-a_i\)，根据 \(\eqref{tag1}\)，如果 \(C\) 比 \(A\) 更优，应当有 \(k_1\geq-a_i\)，矛盾产生，于是此时必然有点 \(A\) 更优。

最后一种情况是 \(-a_i=k_0\)，设此时有 \(k_2<k_0=-a_i<k_1\)，于是 \(A,B\) 两点都要比 \(C\) 更优。

综上，我们可以知道，如果 \(C\) 不在凸包上，那么在凸包上一定存在两点可以替代 \(C\)。

同理，我们可以对于状态转移方程为 \(f_i=\max\limits_{0\leq j<i}\{a_i\cdot b_j + c_i + d_j\}\) 的决策进行证明。

#2.0 决策具有单调性

这里以 「HNOI2008」玩具装箱 作为例题。

#2.1 转移方程及转化

设 \(f_i\) 表示前 \(i\) 个物品的最小代价，不难写出状态转移方程： \[ f_{i}=\min\limits_{0\leq j<i}\left\{f_j+\left(\sum\limits_{k=j+1}^{i}C_k+i-j-1-L\right)^2\right\}, \] 设 \(S_i=i+\sum_{k=1}^iC_i,T=L+1\)，将上式简写为 \[ f_i=\min\limits_{0\leq j<i}\{f_j+(S_i-S_j-T)^2\}, \] 假设从决策点 \(j\) 处转移，应当有 \[ \begin{aligned} f_i&=f_j+(S_i-S_j-T)^2\\ &=f_j+(S_i-T)^2-2S_j(S_i-T)+S_j^2\\ &=f_j+(S_i-T)^2-2S_i\cdot S_j+2S_j\cdot T+S_j^2 \end{aligned} \] 我们将上面的式子转化为如下形式 \[ f_j+2S_j\cdot T+S_j^2=2S_i\cdot S_j+f_i-(S_i-T)^2, \] 这正与 #1.0 简述 中的形式相对应，于是我们的目的是对于斜率 \(2S_i\) 找到一个决策点 \((S_j,f_j+2S_j\cdot T+S_j^2)\) 使得截距 \(f_i-(S_i-T)^2\) 尽可能小。此时已经可以做到 \(O(n\log n)\).

#2.2 决策单调性

我们注意到，\(C_i\) 一定是一个正数，于是 \(2S_i\) 一定单调递增，也意味着我们所需要的斜率一定是单调递增的，且对于所有决策点 \(j\)，其在坐标系上的位置一定是从左到右依次排布的；由上文我们可以知道，可行的决策点一定在凸包上，而下凸包上的线段斜率一定是单调递增的，于是最优决策点应当具有单调性。

同样，这一点我们也可以采用 四边形不等式 进行证明。

我们将 \((S_i-S_j-T)^2\) 作为 \(w(j,i)\)，下面证明 \(w(j,i)\) 满足四边形不等式：

要证明 \(w(j,i)\) 满足四边形不等式，我们只需证明[4] \(w(j,i)\) 满足 \(\forall \ell<r\)，有 \[ w(\ell, r)+w(\ell+1,r+1)\leq w(\ell,r+1)+w(\ell+1,r),\tag2\label{tag2} \] 证明：

设 \(\ell<r\)，有 \[ \begin{aligned} w(\ell,r)=&(S_r-S_{\ell}-T)^2,\\ w(\ell+1,r+1)=&(S_{r+1}-S_{\ell+1}-T)^2=(S_r-S_\ell-T+C_{r+1}+r+1-C_{\ell+1}-\ell-1)\\ =&(S_r-S_\ell-T)^2+(C_{r+1}+r+1-C_{\ell+1}-\ell-1)^2\\ &+2(S_r-S_\ell-T)(C_{r+1}+r+1-C_{\ell+1}-\ell-1)\\ =&(S_r-S_\ell-T)^2+(C_{r+1}+r+1-C_{\ell+1}-\ell-1)^2\\ &+2(S_r-S_\ell-T)(C_{r+1}+r+1)-2(S_r-S_\ell-T)(C_{\ell+1}+\ell+1),\\ w(\ell,r+1)=&(S_{r+1}-S_\ell-T)^2=(S_r-S_\ell+T+C_{r+1}+r+1)^2\\ =&(S_r-S_\ell-T)^2+(C_{r+1}+r+1)^2+2(S_r-S_\ell-T)(C_{r+1}+r+1),\\ w(\ell+1,r)=&(S_r-S_{\ell+1}-T)^2=(S_r-S_\ell+T-(C_{\ell+1}+\ell+1))^2\\ =&(S_r-S_\ell-T)^2+(C_{\ell+1}+\ell+1)^2-2(S_r-S_\ell-T)(C_{\ell+1}+\ell+1),\\ \end{aligned} \] 于是，如果要证明 \(w(\ell, r)+w(\ell+1,r+1)\leq w(\ell,r+1)+w(\ell+1,r)\)，只需证明 \[ (C_{r+1}+r+1-C_{\ell+1}-\ell-1)^2\leq(C_{r+1}+r+1)^2+(C_{\ell+1}+\ell+1)^2,\tag3\label{tag3} \] 而又有 \[ \begin{aligned} (C_{r+1}+r+1-C_{\ell+1}-\ell-1)^2=&(C_{r+1}+r+1)^2+(C_{\ell+1}+\ell+1)^2\\ &-2(C_{r+1}+r+1)(C_{\ell+1}+\ell+1), \end{aligned} \] 又因为 \(C_{r+1},C_{\ell+1},r,\ell\in\mathbb Z^*\)，于是有 \[ -2(C_{r+1}+r+1)(C_{\ell+1}+\ell+1)<0, \] 于是有 \(\eqref{tag3}\) 成立，便可得 \(\eqref{tag2}\) 成立，于是 \(w(j,i)\) 满足四边形不等式。

证毕.

于是，我们已知 \(w(j,i)\) 满足四边形不等式，便可以知道 \(f_i\) 具有决策单调性[5]。

我们便可以利用二分 + 类似单调队列的方式通过维护所有位置的可能最优决策点做到 \(O(n\log n)\)[6].

#2.3 最终实现

事实上， 这道题目不仅具有决策单调性，上面利用决策单调性的时间复杂度中的 \(\log n\) 是因为需要二分查找新的决策从什么时候开始作为可能的最优决策。

实际上， 本题不需要维护所有的最优决策点，我们还是回到斜率优化最富有内涵的图像上来，由于具有决策单调性，于是我们对于 \(i_1<i_2\)，所有在 \(i_1\) 的最优决策点前的决策点对于 \(i_2\) 都不是最优的，可以直接丢掉，这样将不合法的决策点删掉后，在最左边位置的决策点一定是最优决策点；而将 \(i_1\) 作为新决策点加入图像时，该决策点一定只会在右端加入且一定会加入，直接根据凸包的性质将右端不合法的决策点删去就可以了，于是我们可以直接有单调队列进行维护可能还有用的部分凸包，由于每个决策点最多只会入队、出队各一次，转移的时间复杂度为 \(O(1)\)，于是整体的均摊时间复杂度为 \(O(n)\).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#define ll long long

const int N = 100010;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

int n, q[N], frt = 0, tal =  -1; ll L, c[N], s[N], f[N], val[N];

inline ll slope(int x, int y) {return (val[y] - val[x]) / (s[y] - s[x]);}

int main() {
    read(n), read(L); L += 1, q[++ tal] = 0;
    for (int i = 1; i <= n; ++ i) read(c[i]);
    for (int i = 1; i <= n; ++ i) s[i] = s[i - 1] + c[i];
    for (int i = 1; i <= n; ++ i) s[i] += i;
    for (int i = 1; i <= n; ++ i) {
        while (frt < tal && slope(q[frt], q[frt + 1]) < 2 * s[i]) ++ frt;
        f[i] = val[q[frt]] - 2 * s[i] * s[q[frt]] + (s[i] - L) * (s[i] - L);
        val[i] = f[i] + 2 * s[i] * L + s[i] * s[i];
        while (frt < tal && slope(q[tal - 1], q[tal]) >= slope(q[tal - 1], i)) -- tal;
        q[++ tal] = i;
    }
    printf("%lld", f[n]); return 0;
}

#3.0 决策无特殊性质

这里以 「 NOI2007」货币兑换 作为例题。

#3.1 转移方程及转化

题目提示：必然存在一种最优的买卖方案满足：每次买进操作使用完所有的人民币，每次卖出操作卖出所有的金券。

设 \(f_i\) 表示到第 \(i\) 天可以拥有的最大钱数，先写出一个大概的转移方程 \[ f_i=\max\limits_{0<j<i}\{num_A\cdot a_i+num_B\cdot b_i\}, \] 其中 \(num_A\) 与 \(num_B\) 分别表示持有的 \(A\) 金卷的数量与 \(B\) 金卷的数量，这两个数由 \(j\) 决定。显然，第 \(j\) 天买入时，能得到的金卷比例是一定的，于是当天买入时拥有的钱数越大越好，也就是 \(f_j\)，应当有 \[ \begin{aligned} f_j&=num_A\cdot a_j+num_B\cdot b_j\\ f_j&=num_B\cdot R_j\cdot a_j+num_B\cdot b_j\\ num_B&=\dfrac{f_j}{R_j\cdot a_j+b_j}, \end{aligned} \] 同理可得 \[ num_A=\dfrac{f_j\cdot R_j}{R_j\cdot a_j+b_j}, \] 于是我们可以写出完整的状态转移方程 \[ f_i=\max\limits_{0<j<i}\left\{\dfrac{f_j\cdot R_j}{R_j\cdot a_j+b_j}\cdot a_i+\dfrac{f_j}{R_j\cdot a_j+b_j}\cdot b_i\right\}, \] 注意到，转移方程中包含与 \(i\) 和 \(j\) 同时相关的项，优先考虑斜率优化，考虑从决策点 \(j\) 转移，有 \[ f_i=\dfrac{f_j\cdot R_j}{R_j\cdot a_j+b_j}\cdot a_i+\dfrac{f_j}{R_j\cdot a_j+b_j}\cdot b_i, \] 即 \[ \begin{aligned} \dfrac{f_i}{b_i}&=\dfrac{f_j\cdot R_j}{R_j\cdot a_j+b_j}\cdot \dfrac{a_i}{b_i}+\dfrac{f_j}{R_j\cdot a_j+b_j}\\ \dfrac{f_j}{R_j\cdot a_j+b_j}&=-\dfrac{a_i}{b_i}\cdot\dfrac{f_j\cdot R_j}{R_j\cdot a_j+b_j}+\dfrac{f_i}{b_i}, \end{aligned} \] 此时，这个柿子就与我们上面的形式相吻合了，决策点在坐标系上的表示为 \(\left(\frac{f_j\cdot R_j}{R_j\cdot a_j+b_j},\frac{f_j}{R_j\cdot a_j+b_j}\right)\).

一个悲哀的事情出现了，这个式子并没有什么优美的性质，于是实现的恶心程度就上了天。

#3.2 直接维护凸包

首先是最朴素的方式，即采用平衡树维护整个凸包。

查找时，我们可以使用 #1.0 简述 提到的结论，利用二分查找找到以 \(-\frac{a_i}{b_i}\) 为斜率的直线在凸包上的切点。

至于修改时，我们可以先找到它应该插入的位置（凸包上横坐标在其左右的两个紧邻的决策点），然后利用向量叉积来确定当前点是否在当前维护的上凸包以下，如果是，那么直接返回即可；否则从找到的相邻决策点开始删掉不合法的点即可。

这种做法虽然比较好理解，但是实现较为繁琐，且难以直接套用 STL 的 set。

#3.3 CDQ 分治

\(\text{CDQ}(\ell, r)\) 表示计算 \(f_i,i\in[\ell, r]\)，设 \(mid= \left\lfloor\frac{1+ n}2\right\rfloor\)，那么考虑 \(\text{CDQ}(1,n)\)，有

对于 \(i\in[1, mid]\)，我们直接调用 \(\text{CDQ}(1, mid)\) 进行计算，得到这一部分的答案，然后显然 \(i\in [1,mid]\) 这一部分的所有转移点组成的凸壳已经被计算出来了，于是我们考虑 \([1,mid]\) 对于 \([mid+1,n]\) 中的贡献，可以直接建出凸包，然后挨个二分，但是这样实现复杂度又上了一个台阶，于是我们可以先对所有决策点的横坐标排序，再利用栈进行凸包的建立（只需要考虑最右边斜率），注意到凸包上的斜率是单调的，于是然后将 \([mid+1,r]\) 中的所有目标斜率进行排序，利用单调队列进行求解。

再来考虑 \(i\in[mid +1,n]\)，显然最优决策点在 \([1,mid]\) 中的点都已经被更新过了，于是 \([1,mid]\) 这一部分的斜率都已经没用了，可以直接被扔掉；然后直接调用 \(\text{CDQ}(mid + 1,n)\) 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#define ld long double

const int N = 100010;
const int INF = 0x3fffffff;

template <typename T> inline void read(T &x) {
    x = 0; int f = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
    for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
    x *= f;
}

template <typename T> inline T Max(T x, T y) {return x > y ? x : y;}

struct Point {
    ld x, y;

    inline Point() {}
    inline Point(ld _x, ld _y) {x = _x, y = _y;}
    inline bool operator < (const Point b) const {return x == b.x ? y < b.y : x < b.x;}
    inline ld operator ^ (const Point b) const {return x * b.y - y * b.x;}
    inline Point operator - (const Point b) const {return Point(x - b.x, y - b.y);}
} p[N];

int n, s, tmp[N], q[N], slp[N], slp_cp[N]; ld f[N], slope[N], a[N], b[N], r[N];

inline long double Y(int x) {return f[x] / (r[x] * a[x] + b[x]);}
inline long double X(int x) {return Y(x) * r[x];}

inline bool cmp1(int x, int y) {return p[x].x == p[y].x ? p[x].y < p[y].y : p[x].x < p[y].x;}
inline bool cmp2(int x, int y) {return slope[x] > slope[y];}

inline long double get_slope(int x, int y) {return (p[x].y - p[y].y) / (p[x].x - p[y].x);}
inline long double calc(int x, int y) {return p[y].x * a[x] + p[y].y * b[x];}
inline bool illegal(int x1, int x2, int y) {return ((p[y] - p[x2]) ^ (p[x1] - p[x2])) >= 0;}

void cdq(int x, int y) {
    if (x == y) {f[x] = Max(f[x], f[x - 1]), p[x] = Point(X(x), Y(x)); return;}
    int mid = x + y >> 1, frt = 0, tal = -1; cdq(x, mid);
    for (int i = mid + 1; i <= y; ++ i) slp_cp[i] = slp[i];
    sort(tmp + x, tmp + mid + 1, cmp1);
    sort(slp_cp + mid + 1, slp_cp + y + 1, cmp2);
    for (int i = x; i <= mid; ++ i) {
        while (frt < tal && illegal(q[tal - 1], q[tal], tmp[i])) -- tal;
        q[++ tal] = tmp[i];
    }
    for (int i = mid + 1; i <= y; ++ i) {
        while (frt < tal && get_slope(q[frt], q[frt + 1]) > slope[slp_cp[i]]) ++ frt;
        f[slp_cp[i]] = Max(f[slp_cp[i]], calc(slp_cp[i], q[frt]));
    }
    cdq(mid + 1, y);
}

int main() {
    read(n), read(s); f[1] = s;
    for (int i = 1; i <= n; ++ i)
      scanf("%Lf%Lf%Lf", &a[i], &b[i], &r[i]);
    for (int i = 1; i <= n; ++ i) slope[i] = - a[i] / b[i];
    for (int i = 1; i <= n; ++ i) slp[i] = i, tmp[i] = i;
    cdq(1, n); printf("%.3Lf", f[n]); return 0;
}

参考文章