本文主要是介绍论斜率优化dp,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
论斜率优化dp
- 1问题
- 2暴力算法-线性dp
- 3斜率优化线性dp
- 4后记
1问题
如下图
看到这题,题面很复杂
其实可以转化为如下问题
有 n n n个任务,排成一个有序序列,我们要解决这些任务
总费用是每一个任务的完成时间乘以费用系数求和
每个任务之前需要有一个机器启动时间 s s s
也就是说,一开始的时间为 0 0 0,做每个任务之前要先费 s s s的时间启动机器,做每个任务都需要一定时间,假设在 t i ti ti时刻完成费用系数为 f i fi fi的任务,这个任务的费用为 t i × f i ti \times fi ti×fi
总费用为 ∑ t i × f i \sum ti\times fi ∑ti×fi
但是呢,我们可以把若干个任务并做一个,费用系数,完成耗时都求和,只是不需要多次启动机器了
这一看就是线性dp问题, 5000 5000 5000的数据范围也可以支持 n 2 n^2 n2算法
2暴力算法-线性dp
状态的设置很简单,设 d p i dp_i dpi为做完前 i i i个任务的最短耗时
怎么转移,首先枚举 d p j dp_j dpj
d p j dp_j dpj转移到 d p i dp_i dpi需要加些什么?
首先,加上机器启动时间,我们直接把之后所有的费用系数求和再乘以机器启动时间,这就是无后效性
然后,我们考虑 j + 1 j+1 j+1到 i i i的任务合并,所有耗时求和再乘上费用系数求和
因为之前任务已经花费的时间会算到当前任务上,且启动机器时间已经算过了
我们把 1 − i 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 n^2 n2,是正确的
但是这是一道蓝题,肯定不止这点
3斜率优化线性dp
我们发现,枚举 i i i必然不可避免,但是枚举 j j 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 ) dp[i] = dp[j]+sumc[i]*sumt[i]+s*sumc[n]-sumc[j]*(sumt[i]+s) dp[i]=dp[j]+sumc[i]∗sumt[i]+s∗sumc[n]−sumc[j]∗(sumt[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 ] dp[j] = (sumt[i]+s)*sumc[j]+dp[i]-sumt[i]*sumc[i]-s*sumc[n] dp[j]=(sumt[i]+s)∗sumc[j]+dp[i]−sumt[i]∗sumc[i]−s∗sumc[n]
很容易发现, ( s u m t [ i ] + s ) (sumt[i]+s) (sumt[i]+s)和 ( d p [ i ] − s u m t [ i ] ∗ s u m c [ i ] − s ∗ s u m c [ n ] ) (dp[i]-sumt[i]*sumc[i]-s*sumc[n]) (dp[i]−sumt[i]∗sumc[i]−s∗sumc[n])固定,在枚举 j j j的时候,变化的只有 d p [ j ] dp[j] dp[j]和 s u m c [ j ] sumc[j] sumc[j],这不就是一次函数吗, y = k x + b y = kx+b y=kx+b,那么,要让dp[i]尽可能小
d p [ j ] dp[j] dp[j]和 ( s u m t [ i ] + s ) ∗ s u m c [ j ] (sumt[i]+s)*sumc[j] (sumt[i]+s)∗sumc[j]就要尽量接近
我们试着画图
哪个点距离一次函数最近就很明显了
那这有啥用呢
我们可以删去部分点了
用不同斜率的直线尝试求解,删去没有用的点
显然的,一个下凸包,我们动态维护凸包,这样就有了单调性
那么哪个点离直线最近呢,显然是连接两条斜率分别大于和小于当前直线的线段的点
这就可以跑二分了
时间复杂度 n l o g n nlogn nlogn,快了很多
还能再快吗,可以!
我们发现所有费用系数都是正整数, s s s也不变,那么前缀和即 s u m c sumc sumc必然单调递增
直线的斜率也自然是单调递增
这就可以用单调队列维护了,斜率单调递增就行
对于新插入的点,肯定是斜率越小越好,这下动态维护下凸包也可以一并解决
斜率的比较最好交叉相乘,避免误差
附代码(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;
}
4后记
斜率优化代表着本蒟蒻动态规划系列作品的结束
之后还会有插头dp,四边形不等式等内容
不过我太蒻了暂时学不会
本文作者是蒟蒻,如有错误请各位神犇指点
森林古猿出品,必属精品,请认准CSDN森林古猿1
这篇关于论斜率优化dp的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!