斜率优化学习笔记

Posted on |

题外话

今天开始学斜率优化了，以前看过但是看不懂被劝退了。省选马上要到了，还是得逼着自己学下去，要不然只能爆零了。

题目描述

$n$个任务排成一个序列在一台机器上等待完成（顺序不得改变），这$n$个任务被分成若干批，每批包含相邻的若干任务。
从零时刻开始，这些任务被分批加工，第$i$个任务单独完成所需的时间为$t_i$。在每批任务开始前，机器需要启动时间$s$，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。
每个任务的费用是它的完成时刻乘以一个费用系数$f_i$。请确定一个分组方案，使得总费用最小。

初步分析

首先这个题我读了好几遍才读懂……
你可能会问：不分批不是最好的吗，因为这样就只有一次机器启动时间啊。但是你忽略了一个问题，每个任务的完成时间规定为他所在批次的最后一个任务完成的时间，所以分一批不一定最优。
解决了这个问题之后，动态规划转移方程可以尝试写出来。
维护前缀和数组$sumt[ ]$和$sumf[ ]$，分别表示$t[ ]$和$f[ ]$的前缀和。
设$dp[i,j]$表示把前$i$个任务分成$j$批的最小费用。
那么很明显，第$j$批任务的完成时间就是第$j$批中最后一个任务（即$i$）在不分批情况下结束的时间（即$sumt[i]$）加上前面任务需要的开机时间（即$s\times j$）。
于是经典套路：

但是这个算法的时间复杂度为$\mathcal O(n^3)$，需要优化。

费用提前计算优化

根据以往的做题经验，我们尝试把二维化成一维，即让$dp[i]$表示前$i$个任务分批执行的最小费用。
但是这样我们就不知道机器启动过几次了！
别慌，冷静分析一下你会发现，如果我们要从$dp[j]$转移到$dp[i]$的话，由于第$j+1\sim i$都是在同一批内完成的，我们只需要把$s$对$j+1$后的影响补充到费用中就可以了！

时间复杂度$\mathcal O(n^2)$
这就是费用提前计算的思想。

斜率优化分析

他来了。
我们观察费用提前计算优化的式子：

有三个变量：$j,dp[j],dp[i]$。
我们把$\min$去掉，化简一下得到：

这是个$dp[j]$关于$sumf[j]$一次函数，还带有其他变量。
那么斜率就是$(s+sumt[i])$，截距是$dp[i]-sumt[i]\times sumf[i]-s\times sumf[n]$。
我们最终的目的是找到$f[i]$的最小值，其实就是找截距的最小值。
接下来是重头戏！请一定要和我一起在纸上模拟！
我们在坐标系内画出$f[j]$与$sumf[j]$的散点图，用一条斜率为固定正整数的直线自下而上进行平移，第一次接触到一个点的时候就得到了最小截距。
现在我们就需要考虑，对于$j_1<j_2<j_3$，使$j_2$成为最优决策的条件。
我们发现$j_2$在$j_1,j_3$之间，无非就是两个位置：在$j_1,j_3$两点连线上方和下方。
如果将$j_1j_2,j_2j_3$连起来，形象地我们称第一种情况为上凸，第二种情况为下凸。
如果是上凸的话，我们发现，$j_2$永远不可能成为最优决策，因为要么先碰到$j_1$，要么先碰到$j_3$，永远碰不到$j_2$。
如果是下凸的话，$j_2$就有可能成为最优决策。
我们知道对于$f(x)$，连接$(x_1,f(x_1))$和$(x_2,f(x_2))$直线的斜率就是$\frac{f(x_2)-f(x_1)}{x_2-x_1}$，俗称“纵减纵除以横减横”。
所以$j_2$有可能成为最优决策的条件就是：

也就是说我们要维护一个斜率单调递增的下凸壳。
由于$0\leq j<i$，当$i$增加时，就会有新的决策，如果我们只保留连接相邻两点斜率大于$s+sumt[i]$的部分，那么最左端的就是最优决策。

斜率优化具体操作

建立一个单调队列$q$。
对于每个状态变量$i$：

  1. 检查队头$q[l]$与$q[l+1]$，如果$\frac{dp[q[l+1]]-dp[q[l]]}{sumf[q[l+1]]-sumf[q[l]]}\leq s+sumt[i]$，将$q[l]$出队，继续检查新队头。
  2. 取队头$j=q[l]$为最优决策，计算$dp[i]$。
  3. 把$i$插入队尾，在插入之前，若决策点$j_1=q[r-1],j_2=q[r],j_3=i$不满足斜率单调递增，则把$q[r]$出队，继续检查新队尾。

这样时间复杂度就变成了$\mathcal O(n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<bits/stdc++.h>
using namespace std;
const int size=1e6+9;
int n,s;
int sumt[size],sumf[size],dp[size];
int l=1,r=1,q[size];
int main(){
	ios::sync_with_stdio(0);
	memset(dp,0x3f,sizeof(dp));
	cin>>n>>s;
	for(int i=1;i<=n;++i){
		int t,f;
		cin>>t>>f;
		sumt[i]=sumt[i-1]+t;
		sumf[i]=sumf[i-1]+f;
	}
	dp[0]=q[1]=0;
	for(int i=1;i<=n;++i){
		while(l<r&&dp[q[l+1]]-dp[q[l]]<=(s+sumt[i])*(sumf[q[l+1]]-sumf[q[l]])) l++;
		dp[i]=dp[q[l]]-(s+sumt[i])*sumf[q[l]]+sumt[i]*sumf[i]+s*sumf[n];
		while(l<r&&(dp[q[r]]-dp[q[r-1]])*(sumf[i]-sumf[q[r]])>=(dp[i]-dp[q[r]])*(sumf[q[r]]-sumf[q[r-1]])) r--;
		q[++r]=i;
	}
	cout<<dp[n]<<endl;
	return 0;
}
0%