论斜率优化dp

1问题
2暴力算法-线性dp
3斜率优化线性dp
4后记

1问题

如下图
在这里插入图片描述

看到这题，题面很复杂
其实可以转化为如下问题

有 $n$ 个任务，排成一个有序序列，我们要解决这些任务
总费用是每一个任务的完成时间乘以费用系数求和
每个任务之前需要有一个机器启动时间 $s$
也就是说，一开始的时间为 $0$ ，做每个任务之前要先费 $s$ 的时间启动机器，做每个任务都需要一定时间，假设在 $t i$ 时刻完成费用系数为 $f i$ 的任务，这个任务的费用为 $ti \times fi$
总费用为 $\sum ti\times fi$
但是呢，我们可以把若干个任务并做一个，费用系数，完成耗时都求和，只是不需要多次启动机器了
这一看就是线性dp问题， $5000$ 的数据范围也可以支持 $n^2$ 算法

2暴力算法-线性dp

状态的设置很简单，设 $dp_i$ 为做完前 $i$ 个任务的最短耗时
怎么转移，首先枚举 $dp_j$
$dp_j$ 转移到 $dp_i$ 需要加些什么？
首先，加上机器启动时间，我们直接把之后所有的费用系数求和再乘以机器启动时间，这就是无后效性
然后，我们考虑 $j + 1$ 到 $i$ 的任务合并，所有耗时求和再乘上费用系数求和
因为之前任务已经花费的时间会算到当前任务上，且启动机器时间已经算过了
我们把 $1 - i$ 的所有任务耗时求和乘以费用系数即可
上述内容频繁用到求和，可以使用前缀和优化
这个程序很简单，直接附代码(c++)

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

你会发现你AC了，算法的复杂度 $n^2$ ，是正确的
但是这是一道蓝题，肯定不止这点

3斜率优化线性dp

我们发现，枚举 $i$ 必然不可避免，但是枚举 $j$ 就多余了
我们如果能像单调队列优化dp那样直接省去枚举该多好
从状态转移方程入手
先观察
$d p [i] = d p [j] + s u m c [i] * s u m t [i] + s * s u m c [n] - s u m c [j] * (s u m t [i] + s)$
移项得
$d p [j] = (s u m t [i] + s) * s u m c [j] + d p [i] - s u m t [i] * s u m c [i] - s * s u m c [n]$
很容易发现， $(s u m t [i] + s)$ 和 $(d p [i] - s u m t [i] * s u m c [i] - s * s u m c [n])$ 固定，在枚举 $j$ 的时候，变化的只有 $d p [j]$ 和 $s u m c [j]$ ，这不就是一次函数吗， $y = k x + b$ ，那么，要让dp[i]尽可能小
$d p [j]$ 和 $(s u m t [i] + s) * s u m c [j]$ 就要尽量接近
我们试着画图
在这里插入图片描述
哪个点距离一次函数最近就很明显了
那这有啥用呢
我们可以删去部分点了
用不同斜率的直线尝试求解，删去没有用的点

显然的，一个下凸包，我们动态维护凸包，这样就有了单调性
那么哪个点离直线最近呢，显然是连接两条斜率分别大于和小于当前直线的线段的点
这就可以跑二分了
时间复杂度 $n l o g n$ ，快了很多
还能再快吗，可以！
我们发现所有费用系数都是正整数， $s$ 也不变，那么前缀和即 $s u m c$ 必然单调递增
直线的斜率也自然是单调递增
这就可以用单调队列维护了，斜率单调递增就行
对于新插入的点，肯定是斜率越小越好，这下动态维护下凸包也可以一并解决
斜率的比较最好交叉相乘，避免误差
附代码(c++)

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 300010;
int n,s;
LL c[N],t[N];
LL dp[N];
int q[N];
int main(){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];}int hh = 0,tt = 0;dp[0] = 0;for(int i = 1;i<=n;i++){while(hh<tt&&((dp[q[hh+1]])-dp[q[hh]])<=(t[i]+s)*(c[q[hh+1]]-c[q[hh]])){hh++;}int j = q[hh];dp[i] = dp[j]-(t[i]+s)*c[j]+t[i]*c[i]+s*c[n];while(hh<tt&&((dp[q[tt]])-dp[q[tt-1]])*(c[i]-c[q[tt]])>=(dp[i]-dp[q[tt]])*(c[q[tt]]-c[q[tt-1]])){tt--;}q[++tt] = i;}cout<<dp[n];return 0;
}