【动态规划】5 从一次函数出发推导斜率优化dp

背景

基于例题《任务安排》逐步推导进行斜率优化。

引入

例题：P2365 任务安排

考虑动态规划。使用 $d{p}_{i,j}$ 表示前 $i$ 个任务分了 $j$ 段的最小费用。

显然，有 $d{p}_{i,j}={\min }_{k=1}^{i-1}(d{p}_{i,j},d{p}_{k,j-1}+(to{t}_i-to{t}_k))\ast (sum[i]+s\ast j))$​ 。

• $su{m}_i$ 表示 $c_i$ 的前缀和。
• $to{t}_i$ 表示 $t_i$ 的前缀和。

前缀和优化后，时间复杂度 $O(n^3)$，得到 60pts.

代码

#include <bits/stdc++.h>
using namespace std;
int n,s,ans,t[5005],c[5005],dp[5005][5005],sum[5005],tot[5005];
int main()
{cin >> n >> s;for (int i=1;i<=n;i++){cin >> t[i] >> c[i];sum[i] = sum[i-1] + t[i];tot[i] = tot[i-1] + c[i];}memset(dp,0x3f,sizeof(dp));ans = 0x3f3f3f3f;dp[0][0] = 0;for (int i=1;i<=n;i++){for (int j=1;j<=i;j++){for (int k=0;k<i;k++){dp[i][j] = min(dp[i][j],dp[k][j-1] + (tot[i]-tot[k])*(sum[i]+s*j));}	}	}for (int i=1;i<=n;i++){ans = min(ans,dp[n][i]);}cout<<ans;return 0;
}

如何进一步优化呢？

我们发现，可以把有关 $s$ 的计算在前面完成。也就是 费用提前计算 ，就不需要枚举分的段数了。

得到状态转移方程 $d{p}_i=\min (d{p}_i,d{p}_j+su{m}_i\ast to{t}_i-su{m}_i\ast to{t}_j+to{t}_n\ast s-to{t}_j\ast s)$

代码

#include <bits/stdc++.h>
using namespace std;
long long n,s,ans,t[5005],c[5005],dp[5005],sum[5005],tot[5005];
int main()
{cin >> n >> s;for (int i=1;i<=n;i++){cin >> t[i] >> c[i];sum[i] = sum[i-1] + t[i];tot[i] = tot[i-1] + c[i];dp[i] = 1e18;}ans = 1e18;dp[0] = 0;for (int i=1;i<=n;i++){for (int j=0;j<i;j++){dp[i] = min(dp[i],dp[j] + sum[i]*(tot[i]-tot[j]) + (tot[n]-tot[j])*s);}	}cout<<dp[n];return 0;
}

正文

状态转移方程 $d{p}_i=\min (d{p}_i,d{p}_j+su{m}_i\ast to{t}_i-su{m}_i\ast to{t}_j+to{t}_n\ast s-to{t}_j\ast s)$

把与 $i,j$ 有关的各单独放在一起，得到 $d{p}_i=\min (d{p}_i,d{p}_j+su{m}_i\ast to{t}_i+to{t}_n\ast s-to{t}_j\ast (su{m}_i+s))$

去掉最小值，得到 $d{p}_i=d{p}_j+su{m}_i\ast to{t}_i+to{t}_n\ast s-to{t}_j\ast (su{m}_i+s)$

移项，得到 $d{p}_j=to{t}_j\ast (su{m}_i+s)+d{p}_i-su{m}_i\ast to{t}_i-to{t}_n\ast s$

在 $to{t}_j$ 为横坐标，$d{p}_j$ 为纵坐标的平面直角坐标系中，

这是一条 $y=(s+su{m}_i)\ast x+d{p}_i-su{m}_i\ast to{t}_i-to{t}_n\ast s$ 的直线。

写成 $y=kx+b$ 的形式，$k=s+su{m}_i$ ，$b=d{p}_i-su{m}_i\ast to{t}_i-to{t}_n\ast s$.

由于 $k$ 是定值，所求的 $d{p}_i$ 存在于 $b$ 中，所以我们只需要找到最小的 $b$ 即可。

---

如何寻找最小的 $b$ ？

发现有一些点会出现在这条直线上，我们把这样的点称为 决策点，即 $(to{t}_j,d{p}_j)$。

对于这些决策点，由于 $k$ 是定值，所以有且只有一条 $k=s+su{m}_i$ 的直线经过一个决策点，这些决策点一共会产生不超过 $j$ 条直线。

对于已知的一个决策点 $(to{t}_j,d{p}_j)$，我们把它们带入到一次函数表达式里去，就能解出一个 $b$ ，枚举 $j$ 得到最小的 $b$ 即可。

但这种方法过于朴素，时间复杂度不变。考虑优化。

由于我们是从决策点出发，推导 $b$ 的值。则说明决策点坐标（或者说 $j$ ）与 $b$ 之间存在线性关系。考虑决策点坐标之间的关系来优化。

对于三个决策点 $(to{t}_{j_1},d{p}_{j_1}),(to{t}_{j_2},d{p}_{j_2}),(to{t}_{j_3},d{p}_{j_3})$ （我们设这三点 $j_1<j_2<j_3$ ，由于 $t,c>0$ ，所以这三点的横坐标依次递增，即 $to{t}_{j_1}<to{t}_{j_2}<to{t}_{j_3}$）来说，当这三个决策点有且仅有取 $(to{t}_{j_2},d{p}_{j_2})$ 时，$b$ 有最小值，那么这三点所构成的直线不会两两重合，并分为两种情况：

情况 1 ($j_2$ 在 $j_1$ 与 $j_3$ 的连线上方)

当这三点构成一个向上凸出的形状，即 上凸 。显然此时 $j_2$ 一定不会使得 $b$ 取最小值，如下图所示。

情况 2 ($j_2$ 在 $j_1$ 与 $j_3$ 的连线下方)

当这三点构成一个向下凸出的形状，即 下凸 。显然此时 $j_2$ 可能使得 $b$ 取最小值，如下图所示。

发现只有 下凸 的情况 ($j_2$ 在 $j_1$ 与 $j_3$ 的连线下方) 才可能使 $j_2$ 取到最小的 $b$ 。

则有 $\frac{d{p}_{j_2}-d{p}_{j_1}}{to{t}_{j_2}-to{t}_{j_1}}<\frac{d{p}_{j_3}-d{p}_{j_2}}{to{t}_{j_3}-to{t}_{j_2}}$ 。

即直线 $j_1\to j_2$ 的 $k$ 小于 $j_2\to j_3$ 直线的 $k$ ，本质上是这两条直线的斜率关系。

---

因此，我们需要维护 相邻两点间直线的 $k$ （斜率） ，并当它们 单调递增 时， $j_2$ 所得到的 $b$ 就可能是最小值。

那么什么时候 $j_2$ 所取的 $b$ 就一定是最小值呢？

我们发现，当一段单调递增的 $k$ 满足一个点的左边的 $k’$ 都小于 $k$ ，右边的 $k’$ 都大于 $k$ 时，这个点就是使 $b$ 最小的点。

如果我们只维护 相邻两点间连线斜率大于等于 $k$ 的 $k^{\prime }$ （斜率），那么在这个单调递增的序列中最小值就能使 $b$ 最小。

这不就是单调队列的思路吗？

总结一下：

1. 我们用单调队列维护相邻两点间直线的 $k$ ，使其单调递增。
2. 在单调队列里放的是 $k$ 单调递增的点的编号。
3. 最终答案是单调队列的队头坐标代入 $d{p}_i=d{p}_j+su{m}_i\ast to{t}_i+to{t}_n\ast s-to{t}_j\ast (su{m}_i+s)$.
4. 为了维护单调性，我们需要从左侧队头开始删除。即判断队头斜率 $\frac{d{p}_{q_{head+1}}-d{p}_{q_{head}}}{to{t}_{q_{head+1}}-to{t}_{q_{head}}}\le s+su{m}_i$ 时，把队头出队即可。 为了避免精度问题，且 $tot$ 有单调递增性，那么我们不妨判断 $d{p}_{q_{head+1}}-d{p}_{q_{head}}\le (s+su{m}_i)\ast (to{t}_{q_{head+1}}-to{t}_{q_{head}})$.
5. 添加时，如果 $q_i$ 不能与前面的点满足单调性，那么直接把前面的点不断出队，直到满足单调性为止。即当 $\frac{d{p}_i-d{p}_{q_{tail}}}{to{t}_i-to{t}_{q_{tail}}}\le \frac{d{p}_{q_{tail}}-d{p}_{q_{tail-1}}}{to{t}_{q_{tail}}-to{t}_{q_{tail-1}}}$ 时不断出队即可。同样避免精度问题，判断 $(d{p}_i-d{p}_{q_{tail}})\ast (to{t}_{q_{tail}}-to{t}_{q_{tail-1}})\le (d{p}_{q_{tail}}-d{p}_{q_{tail-1}})\ast (to{t}_i-to{t}_{q_{tail}})$ 即可。

时间复杂度 $O(n)$ .

#include <bits/stdc++.h>
using namespace std;
const int N = 300005;
long long n,s,ans,t[N],c[N],dp[N],sum[N],tot[N];
long long q[N],head=1,tail=1;
int main()
{cin >> n >> s;for (int i=1;i<=n;i++){cin >> t[i] >> c[i];sum[i] = sum[i-1] + t[i];tot[i] = tot[i-1] + c[i];dp[i] = 1e18;}ans = 1e18;dp[0] = 0;for (int i=1;i<=n;i++){while (head < tail && dp[q[head+1]]-dp[q[head]] <= (s+sum[i])*(tot[q[head+1]]-tot[q[head]])) head++;dp[i] = dp[q[head]] + sum[i]*tot[i] + tot[n]*s - tot[q[head]]*(sum[i]+s);while (head < tail && (dp[i]-dp[q[tail]])*(tot[q[tail]]-tot[q[tail-1]]) <= (dp[q[tail]]-dp[q[tail-1]])*(tot[i]-tot[q[tail]])) tail--;q[++tail] = i;}cout<<dp[n];return 0;
}

为什么单调队列初始 head = 1,tail = 1 ，而不能写作 head = 1,tail = 0 ?
考虑到还有 dp[0] = 0 ，要么把 tail 设为 head ，要么把 tail 设为 head-1 再在队列里加入 dp[0]。

后记

斜率优化看起来好像的确比想象中抽象很多，希望对大家理解斜率优化有所帮助！