「DP 浅析」斜率优化
admin
撰写于 2022年 01月 22 日

#0.0 屑在前面

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

#1.0 简述

#1.1 适用情况

斜率优化一般适用于状态转移方程如下的 DP

\[f_i=\mathop{\min/\max}\limits_{0\leq j\]

其中 \(a_i,b_j,c_i, d_j\) 在计算 \(f_i\) 时都是常数(已知量)。

#1.2 大致思想

为了方便叙述,下文中的方程都采用 \(f_i=\min\limits_{0\leq 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\)。

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

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

这里状态转移方程依旧都采用 \(f_i=\min\limits_{0\leq j

设 \(0\leq 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}\end{cases}
\]

如果我们将决策点表示为 \((b_j,d_j)\),那么此时不等号右边是斜率式的形式。

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

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

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

第二种情况是 \(-a_i>k_0\),此时显然有 \(\overline{AC}\) 的斜率 \(k_2

最后一种情况是 \(-a_i=k_0\),设此时有 \(k_2

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

同理,我们可以对于状态转移方程为 \(f_i=\max\limits_{0\leq j

#2.0 决策具有单调性

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

#2.1 转移方程及转化

设 \(f_i\) 表示前 \(i\) 个物品的最小代价,不难写出状态转移方程:

\[f_{i}=\min\limits_{0\leq j\]

设 \(S_i=i+\sum_{k=1}^iC_i,T=L+1\),将上式简写为

\[f_i=\min\limits_{0\leq j\]

假设从决策点 \(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

\[w(\ell, r)+w(\ell+1,r+1)\leq w(\ell,r+1)+w(\ell+1,r),\tag2
\]

证明

设 \(\ell

\[\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
\]

而又有

\[\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,
\]

于是有 \((3)\) 成立,便可得 \((2)\) 成立,于是 \(w(j,i)\) 满足四边形不等式。

证毕.

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

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

#2.3 最终实现

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

实际上, 本题不需要维护所有的最优决策点,我们还是回到斜率优化最富有内涵的图像上来,由于具有决策单调性,于是我们对于 \(i_1

#define ll long long

const int N = 100010;
const int INF = 0x3fffffff; template 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) / (s[y] - s);} 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\]

其中 \(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\]

注意到,转移方程中包含与 \(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)\) 即可。

#define ld long double

const int N = 100010;
const int INF = 0x3fffffff; template 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 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 / (r * a + b);}
inline long double X(int x) {return Y(x) * r;} inline bool cmp1(int x, int y) {return p.x == p[y].x ? p.y < p[y].y : p.x < p[y].x;}
inline bool cmp2(int x, int y) {return slope > slope[y];} inline long double get_slope(int x, int y) {return (p.y - p[y].y) / (p.x - p[y].x);}
inline long double calc(int x, int y) {return p[y].x * a + p[y].y * b;}
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 = Max(f, f[x - 1]), p = 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;
}

参考文章

  • [1] 斜率优化 - OI Wiki
  • [2] 【学习笔记】动态规划—斜率优化DP(超详细)- 辰星凌
  • [3] 斜率优化 - T_X蒻
  • [4] [5] [6] 「DP 浅析」四边形不等式优化 - Dfkuaid

「DP 浅析」斜率优化的

「DP 浅析」斜率优化

#0.0 屑在前面

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

#1.0 简述

#1.1 适用情况

斜率优化一般适用于状态转移方程如下的 DP

\[f_i=\mathop{\min/\max}\limits_{0\leq j\]

其中 \(a_i,b_j,c_i, d_j\) 在计算 \(f_i\) 时都是常数(已知量)。

#1.2 大致思想

为了方便叙述,下文中的方程都采用 \(f_i=\min\limits_{0\leq 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\)。

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

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

这里状态转移方程依旧都采用 \(f_i=\min\limits_{0\leq j

设 \(0\leq 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}\end{cases}
\]

如果我们将决策点表示为 \((b_j,d_j)\),那么此时不等号右边是斜率式的形式。

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

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

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

第二种情况是 \(-a_i>k_0\),此时显然有 \(\overline{AC}\) 的斜率 \(k_2

最后一种情况是 \(-a_i=k_0\),设此时有 \(k_2

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

同理,我们可以对于状态转移方程为 \(f_i=\max\limits_{0\leq j

#2.0 决策具有单调性

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

#2.1 转移方程及转化

设 \(f_i\) 表示前 \(i\) 个物品的最小代价,不难写出状态转移方程:

\[f_{i}=\min\limits_{0\leq j\]

设 \(S_i=i+\sum_{k=1}^iC_i,T=L+1\),将上式简写为

\[f_i=\min\limits_{0\leq j\]

假设从决策点 \(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

\[w(\ell, r)+w(\ell+1,r+1)\leq w(\ell,r+1)+w(\ell+1,r),\tag2
\]

证明

设 \(\ell

\[\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
\]

而又有

\[\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,
\]

于是有 \((3)\) 成立,便可得 \((2)\) 成立,于是 \(w(j,i)\) 满足四边形不等式。

证毕.

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

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

#2.3 最终实现

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

实际上, 本题不需要维护所有的最优决策点,我们还是回到斜率优化最富有内涵的图像上来,由于具有决策单调性,于是我们对于 \(i_1

#define ll long long

const int N = 100010;
const int INF = 0x3fffffff; template 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) / (s[y] - s);} 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\]

其中 \(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\]

注意到,转移方程中包含与 \(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)\) 即可。

#define ld long double

const int N = 100010;
const int INF = 0x3fffffff; template 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 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 / (r * a + b);}
inline long double X(int x) {return Y(x) * r;} inline bool cmp1(int x, int y) {return p.x == p[y].x ? p.y < p[y].y : p.x < p[y].x;}
inline bool cmp2(int x, int y) {return slope > slope[y];} inline long double get_slope(int x, int y) {return (p.y - p[y].y) / (p.x - p[y].x);}
inline long double calc(int x, int y) {return p[y].x * a + p[y].y * b;}
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 = Max(f, f[x - 1]), p = 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;
}

参考文章

  • [1] 斜率优化 - OI Wiki
  • [2] 【学习笔记】动态规划—斜率优化DP(超详细)- 辰星凌
  • [3] 斜率优化 - T_X蒻
  • [4] [5] [6] 「DP 浅析」四边形不等式优化 - Dfkuaid

「DP 浅析」斜率优化的

赞 (0)

猜您想看

评论区(暂无评论)

这里空空如也,快来评论吧~

我要评论