斜率优化学习笔记seo优化

斜率优化学习笔记

news/2024/10/4 12:54:19

斜率优化模板题，有三倍经验，难度逐渐递增，建议从前做到后。

P2365 任务安排，P10979 任务安排 2，P5785 [SDOI2012] 任务安排。

（但是我这种做法 P10979 和 P5785 没有区别。

思路：

设 \(f_i\) 表示第 \(i\) 个任务加工后所需的最小总费用，那么就有转移式。

\[f_i=\displaystyle\min_{j=0}^{i-1}\{f_j+\sum_{k=j+1}^i{((\sum_{l=1}^i T_l+num\times s)\times C_k)}\}=\min_{j=0}^{i-1}\{f_j+(\sum_{k=1}^i T_k+num\times s)\times\sum_{k=j+1}^i C_k\} \]

\(num\) 表示在这批任务完成之前分了多少批任务。

但是 \(num\) 的值关乎到前面转移的值，要再开一维吗？不需要，这里采用费用前置的思想。由于每分一组，num就会多一，根据 \(\sum_{k=1}^i T_k+num\times s\)，后面的每个任务 \(k\) 就会多贡献 \(s\times C_k\)，那么转移式就变成了：

\[f_i=\displaystyle\min_{j=0}^{i-1}\{f_j+\sum_{k=1}^i T_k\times\sum_{k=j+1}^i C_k+\sum_{k=j+1}^n C_k\times s\} \]

观察到转移式的 \(\sum\) 都是可以用前缀和维护的，对 \(T,C\) 数组进行前缀和（为了方便书写，不加说明的 \(T,C\) 数组表示已经前缀和完了的数组），那么转移式为：

\[f_i=\displaystyle\min_{j=0}^{i-1}\{f_j+T_i\times(C_i-C_j)+(C_n-C_j)\times s\} \]

动态规划的转移参照 P2365 任务安排的这篇题解。

下面讲一个不太常用的斜率优化方法。

我们先把转移式做一些变化：

\[f_i=\displaystyle\min_{j=1}^{i-1}\{f_j-C_j\times(T_i+s)\}+T_i\times C_i+C_n\times s \]

即把常数项提到 \(\min\) 外，在合并同类项。

上述转移式，时间复杂度瓶颈是找到最优决策点，所以我们考虑两个决策点 \(j_1,j_2\)，考虑若决策点 \(j_1\) 优于决策点 \(j_2\)，那么：

\[f_{j_1}-C_{j_1}\times(T_i+s)<f_{j_2}-C_{j_2}\times(T_i+s) \]

\[(C_{j_2}-C_{j_1})\cdot(T_i+s)<f_{j_2}-f_{j_1} \]

现在我们钦定 \(C_{j_2}>C_{j_1}\)（注意不是 \(j_2>j_1\)，后面再说为什么），那么我们可以把 \((C_{j_2}-C_{j_1})\) 除到不等式的右边，即：

\[\frac{f_{j_2}-f_{j_1}}{C_{j_2}-C_{j_1}}>T_i+s \]

不等式的左边是不是很像斜率式？我们令 \(P_{i}\) 为二维平面直角坐标系的点 \((C_i,f_i)\)，那么不等式的左边可以表示为 \(k_{P_{j_1},P_{j_2}}\) 即点 \(P_{j_1}\) 和点 \(P_{j_2}\) 之间的斜率。

该不等式可以用文字描述为：若两点之间的斜率大于 \(T_i+s\)，那么左边的点更优，否则右边的点更优（等号取到的情况即为两个点一样优秀，选哪个无所谓，不做细分）、

我们现在考虑三个点的情况，若这三个点 \(A,B,C\) 围成一个上凸壳（假设左右顺序为 \(A,B,C\)），那么直线 \(AB\)，直线 \(BC\) 和斜率为 \(T_i+s\) 的直线有下面三种关系：

直线 \(AB\) 和直线 \(BC\) 的斜率都大于 \(T_i+s\)，此时 \(A\) 点优于 \(B\) 点，\(B\) 点优于 \(C\) 点，\(B\) 点不是最优的。
直线 \(AB\) 的斜率大于 \(T_i+s\)，直线 \(BC\) 的斜率小于 \(T_i+s\)，此时 \(A\) 点优于 \(B\) 点，\(C\) 点优于 \(B\) 点，\(B\) 点不是最优的。
直线 \(AB\) 和直线 \(BC\) 的斜率都小于 \(T_i+s\)，此时 \(B\) 点优于 \(A\) 点，\(C\) 点优于 \(B\) 点，\(B\) 点不是最优的。

综上，若三个点围成一个上凸壳，那么中间的那个点一定不是最优的（其实画图更好理解）。

现在考虑转移 \(i\)，根据上面的性质，我们可以将 \(i\) 之前的所有点维护一个下凸壳，由于两点之间的斜率大于 \(T_i+s\) 则左边的点更优，我们可以找到第一个 \(j\)，使得 \(P_j\) 与 \(P_{j+1}\) 的斜率大于 \(T_i+s\) 的点，若没有这个点，那么凸壳的最后一个点最优，然后用这个点的来更新 \(i\) 的 dp 值，这个点可以通过二分找到。

然后考虑如何维护这个下凸壳，这个还是比较容易想到，假设在此之前已经维护好了之前所有点的下凸壳，需要加上该点。由于 \(C_i\)（不是前缀和数组）是非负的，那么 \(C_i\) 是单调的，即点的横坐标是单调的，所以我们可以直接在下凸壳的最后加点。若新加上该点，点集不构成下凸壳，那么将最后一个点去掉反复循环，直到新加上该点可以构成下凸壳，或者下凸壳中没有点了结束。根据这个算法，我们可以用一个单调栈维护下凸壳。

这道题就做完了。

对于这种做法 P10979 任务安排 2 和 P5785 [SDOI2012] 任务安排没有区别，因为这两道题的 \(C_i\) 都是非负整数（不是前缀和数组），这就使每个点的横坐标是单调的，而这个算法没有限制 \(T_i\)（不是前缀和数组）的正负，即并不需要要求决策单调性。

昨完这道题，我们分析一下什么题可以用斜率优化，首先他要求出一段区间的某个函数值的极值，而这个函数值中包含 \(i\) 与 \(j\) 的交叉项，这样的题目大概率是斜率优化。

现在来讲为什么我们是要钦定 \(C_{j_2}>C_{j_1}\) 而不是钦定 \(j_2>j_1\)，有的同学可能会认为钦定 \(j_2>j_1\)，不就是和钦定 \(x_{j_2}>x_{j_1}\)（\(x_i\) 为点 \(i\) 的横坐标）一样的吗？为什么不行。对于比较简单的斜率优化题目来说，这样是可以的包括这道题，但是有一些题目的点的横坐标并不是单调的，就导致每次加点的时候就不能按照编号顺序一个一个加点，而是要按照点的横坐标顺序来加点，否则你的思路会十分混乱。对于这种题目我们可以用 cdq 分治或者用平衡树维护凸壳解决。

代码：

#include <bits/stdc++.h>using namespace std;const int kMaxN = 3e5 + 5;int n, s, t[kMaxN], c[kMaxN], top, L, R, M;
long long f[kMaxN];struct P {int x;long long y;
} stk[kMaxN];long double slope(P i, P j) { return i.x == j.x ? (i.y > j.y ? -4e18 : 4e18) : (long double)(i.y - j.y) / (i.x - j.x); }int main() {ios::sync_with_stdio(0), cin.tie(0);cin >> n >> s;for (int i = 1; i <= n; i++) {cin >> t[i] >> c[i], t[i] += t[i - 1], c[i] += c[i - 1];}for (int i = 1; i <= n; i++) {for (; top > 1 && slope(stk[top - 1], stk[top]) > slope(stk[top], {c[i - 1], f[i - 1]}); top--) {}stk[++top] = {c[i - 1], f[i - 1]}, L = 1, R = top, M = L + R >> 1;for (; L < R; M = L + R >> 1) {(M == top ? 4e18 : slope(stk[M], stk[M + 1])) > s + t[i] ? R = M : L = M + 1;}f[i] = stk[L].y - 1LL * (s + t[i]) * stk[L].x + 1LL * s * c[n] + 1LL * c[i] * t[i];}cout << f[n];return 0;
}

作为一篇斜率优化的学习笔记，还是讲一道点的横坐标不单调的例题吧（毕竟这种方法比较常见），例题：P4655 [CEOI2017] Building Bridges。