信息学奥赛一本通 1607：【 例 2】任务安排 2 | 洛谷 P10979 任务安排 2

【题目链接】

ybt 1607：【 例 2】任务安排 2
洛谷 P10979 任务安排 2
注：ybt1607中n最大达到$10^4$，洛谷P10979中n最大达到$3\ast 10^5$，本题解统一认为n最大达到$3\ast 10^5$。

【题目考点】

1. 动态规划：斜率优化动规

2. 单调队列

数组实现单调队列代码操作：

操作	代码
单调队列初始化	int q[N], l = 1, r = 0
单调队列是否为空	l > r（队列不空：l <= r）
取队头	q[l]
取队尾	q[r]
队尾入队	q[++r] = a
队头出队	++l
队尾出队	--r

【解题思路】

与本题题面相同但问题规模较小的题目：
信息学奥赛一本通 1606：【 例 1】任务安排 1 | 洛谷 P2365 任务安排
本题相比上题只有n的数值范围扩大到了$3\ast 10^5$，因此理论上不能再使用$O(n^2)$的算法，应该使用$O(nlogn)$或$O(n)$的算法。状态定义和状态转移方程分析过程见上题中的解法2。
以下介绍的就是动态规划的斜率优化算法：

1. 整理状态转移方程

状态定义：$d{p}_i$：前i个任务的所有子段划分方案中，执行任务的费用 加上当前方案下每批任务的启动时间对后续任务产生的费用 加和最小的任务批次划分方案的费用。
第i个任务执行时间为$t_i$，其前缀和为$T$。第i个任务的费用系数为为$c_i$，其前缀和为$C$
状态转移方程： d p i = m i n { d p j + T i ⋅ ( C i − C j ) + s ⋅ ( C n − C j ) } , 0 ≤ j < i dp_i = min\{dp_j+T_i\cdot (C_i-C_j)+s\cdot (C_n-C_j)\}, 0\le j< i dpi​=min{dpj​+Ti​⋅(Ci​−Cj​)+s⋅(Cn​−Cj​)},0≤j<i
将与j有关以及无关的项分开写，得到：
d p i = m i n { d p j − ( T i + s ) ⋅ C j + T i ⋅ C i + s ⋅ C n } , 0 ≤ j < i dp_i = min\{dp_j-(T_i+s)\cdot C_j+T_i\cdot C_i+s\cdot C_n\}, 0\le j<i dpi​=min{dpj​−(Ti​+s)⋅Cj​+Ti​⋅Ci​+s⋅Cn​},0≤j<i

2. 决策点

每个j的取值称为一个决策点。假设$d{p}_{j_1}<d{p}_{j_2}$，也就是决策点$j_1$优于$j_2$，
则$d{p}_{j_1}-(T_i+s)\cdot C_{j_1}+T_i\cdot C_i+s\cdot C_n<d{p}_{j_2}-(T_i+s)\cdot C_{j_2}+T_i\cdot C_i+s\cdot C_n$
$d{p}_{j_1}-(T_i+s)\cdot C_{j_1}<d{p}_{j_2}-(T_i+s)\cdot C_{j_2}$
$(T_i+s)\cdot (C_{j_2}-C_{j_1})<d{p}_{j_2}-d{p}_{j_1}$
如果已知$C_{j_1}<C_{j_2}$，那么$\frac{d{p}_{j_2}-d{p}_{j_1}}{C_{j_2}-C_{j_1}}>T_i+s$
反过来，已知$C_{j_1}<C_{j_2}$
如果$\frac{d{p}_{j_2}-d{p}_{j_1}}{C_{j_2}-C_{j_1}}>T_i+s$，那么决策点$j_1$优于$j_2$
如果$\frac{d{p}_{j_2}-d{p}_{j_1}}{C_{j_2}-C_{j_1}}<T_i+s$，那么决策点$j_2$优于$j_1$

3. 决策点的几何表示

对于每个j，都能得到一组数对$(C_j,d{p}_j)$，将这组数对看作平面直角坐标系中的一个点，称为第j点$(x_j,y_j)$，其横纵坐标分别为$x_j=C_j，y_j=d{p}_j$。
那么$k(j_1,j_2)=\frac{y_{j_2}-y_{j_1}}{x_{j_2}-x_{j_1}}=\frac{d{p}_{j_2}-d{p}_{j_1}}{C_{j_2}-C_{j_1}}$就是第$j_1$点和第$j_2$点连线的斜率。

4. 转为线性规划问题

将状态转移方程
d p i = m i n { d p j − ( T i + s ) ⋅ C j + T i ⋅ C i + s ⋅ C n } , 0 ≤ j < i dp_i = min\{dp_j-(T_i+s)\cdot C_j+T_i\cdot C_i+s\cdot C_n\}, 0\le j<i dpi​=min{dpj​−(Ti​+s)⋅Cj​+Ti​⋅Ci​+s⋅Cn​},0≤j<i
去掉min，$C_j$替换为$x$，$d{p}_j$替换为y，得到：
$d{p}_i=y-(T_i+s)x+T_i\cdot C_i+s\cdot C_n$
移项得：$y=(T_i+s)x+d{p}_i-T_i\cdot C_i-s\cdot C_n$
这是一条斜率为$T_i+s$，截距为$d{p}_i-T_i\cdot C_i-s\cdot C_n$的直线。
记直线斜率$K=T_i+s$，截距$B=d{p}_i-T_i\cdot C_i-s\cdot C_n$，该直线可以表示为$y=Kx+B$
显然，该直线的斜率是固定的，截距中只有$d{p}_i$是可以变化的，也就是说$B$越小$d{p}_i$越小。
原状态转移方程要完成的事是：在$0\le j<i$范围内选择一个j使得$d{p}_i$的值最小。
该问题等价于在$0\le j<i$范围内选择一个决策点j，使得斜率固定的直线$y=Kx+B$在经过点$(C_j,d{p}_j)$时，截距B最小。
使截距B最小的决策点j，也就是使$d{p}_i$最小的j，称为最优决策点。

5. 决策点的比较条件

决策点比较条件可以写为：
已知$C_{j_1}<C_{j_2}$

• 如果$k(j_1,j_2)>K$，那么决策点$j_1$优于$j_2$，也就是两点连线斜率大于直线斜率，左侧点更优。
• 如果$k(j_1,j_2)<K$，那么决策点$j_2$优于$j_1$，也就是两点连线斜率小于直线斜率，右侧点更优。

图示：

$k(j_1,j_2)<K$，所以$j_2$优于$j_1$
$k(j_2,j_3)>K$，所以$j_2$优于$j_3$

6. 上凸点与下凸点

已知有$j_1,j_2,j_3$三个点满足$C_{j_1}<C_{j_2}<C_{j_3}$

• 如果$k(j_1,j_2)<k(j_2,j_3)$，称$j_2$为下凸点。
• 如果$k(j_1,j_2)>k(j_2,j_3)$，称$j_2$为上凸点。
  在选最优决策点时可以忽略上凸点

证明：假设$j_2$是$j_1,j_2,j_3$三个点中的上凸点，
如果$k(j_1,j_2)>K$，则决策点$j_1$优于$j_2$。
如果$K>k(j_1,j_2)>k(j_2,j_3)$，那么决策点$j_3$优于$j_2$。
如果$K=k(j_1,j_2)$，那么选$j_1$和选$j_2$是一样的，可以不选$j_2$。

图示：
$k(j_1,j_2)<k(j_2,j_3)$，$j_2$为下凸点，$j_2$可能是最优决策点。
$k(j_1,j_4)>k(j_4,j_3)$，$j_4$为上凸点，$j_4$不可能是最优决策点。

7. 下凸壳

决策点的点集中，只有下凸点有可能作为最优决策点，因此我们只需要维护所有下凸点构成的下凸壳。
下凸壳上的点按$C_j$从小到大记为$q_l,q_{l+1},...,q_r$

由于所有决策点都是下凸点，
所以$k(q_l,q_{l+1})<k(q_{l+1},q_{l+2})<...<k(q_{r-1},q_r)$
相邻点连成的线段的斜率是单调递增的。因此使用单调队列维护下凸壳。

8. 决策点队头出队

随着队列q下标x增大，决策点编号$j=q_x$单调递增，$C_j$也单调递增
本题中直线斜率$K=T_i+s$随着i的增大是单调递增的。
因此如果当前选择决策点$j$，对于横坐标小于$C_j$的决策点，也就是队列中$j$前面的决策点都不可能再成为最优决策点，因此不需要再维护了。
具体做法为：
不断比较$k(q_l,q_{l+1})$和$K$的大小

• 只要$k(q_l,q_{l+1})\le K$，则队头$q_l$出队
• 直到队列里只有一个点或$k(q_l,q_{l+1})>K$，此时$q_l$为最优决策点。

将最优决策点$q_l$带入状态转移方程，得出新的状态$d{p}_i$，以及新的决策点i。

图示：
$k(q_1,q_2)\le K$，则队头$q_1$出队；
$k(q_2,q_3)\le K$，则队头$q_2$出队；
$k(q_3,q_4)>K$，队头$q_3$是最优决策点。

9. 决策点队尾入队

求出状态$d{p}_i$后，就得到一个新的决策点第$i$点，其坐标为$(C_i,d{p}_i)$。我们需要将该点加入决策点集。
由于$C_i$随着i的增大单调递增，因此新的决策点$i$一定在下凸壳最后一个决策点$q_r$的右侧。
如果新增第$i$点导致下凸壳上最后一个决策点$q_r$变为上凸点，则将$q_r$点去掉，直到不产生上凸点时，将第i点加入决策点集的下凸壳。
具体做法：
不断比较$k(q_r,i)$和$k(q_{r-1},q_r)$的大小

• 只要$k(q_{r-1},q_r)\ge k(q_r,i)$，则将队尾$q_r$出队
• 直到队列中只有一个点或$k(q_{r-1},q_r)$<$k(q_r,i)$，此时将$i$队尾入队。
  
  图示：
  $k(q_3,q_4)\ge k(q_4,i)$，则将队尾$q_4$出队。
  $k(q_2,q_3)<k(q_3,i)$，则将i队尾入队。

10. 十字相乘

在具体计算时，应避免使用实数除法导致精度丢失，应该使用十字相乘法，在整数域内进行计算和比较。

• 判断$k(q_l,q_{l+1})\le K$，即判断$\frac{d{p}_{q_{l+1}}-d{p}_{q_l}}{C_{q_{l+1}}-C_{q_l}}\le T_i+s$
  等价于判断$d{p}_{q_{l+1}}-d{p}_{q_l}\le (T_i+s)(C_{q_{l+1}}-C_{q_l})$
• 判断$k(q_{r-1},q_r)\ge k(q_r,i)$，即判断$\frac{d{p}_i-d{p}_{q_r}}{C_i-C_{q_r}}\le \frac{d{p}_{q_r}-d{p}_{q_{r-1}}}{C_{q_r}-C_{q_{r-1}}}$
  等价于判断$(d{p}_i-d{p}_{q_r})(C_{q_r}-C_{q_{r-1}})\le (d{p}_{q_r}-d{p}_{q_{r-1}})(C_i-C_{q_r})$

11. 其它

初始时已知$d{p}_0=0$，应该先把第0点加入单调队列
最终结果是$d{p}_n$
单调队列判断队列是否为空：l > r，判断队列不空：l <= r，判断队列中元素个数是否大于1个l < r。
注意dp数组要设为long long类型。
本问题经过斜率优化后，算法时间复杂度为$O(n)$

【题解代码】

解法1：斜率优化动规 $O(n)$

#include<bits/stdc++.h>
using namespace std;
#define N 300005
long long n, s, t[N], c[N], T[N], C[N], dp[N];//dp[i]:前i个任务的所有子段划分方案中，执行任务的费用 加上当前方案下每批任务的启动时间对后续任务产生的费用加和 最小的划分方案的费用
int q[N], l = 1, r = 0;//单调队列 
int main()
{cin >> n >> s;for(int i = 1; i <= n; ++i){cin >> t[i] >> c[i];T[i] = T[i-1]+t[i];//T:t的前缀和C[i] = C[i-1]+c[i];//C:c的前缀和}q[++r] = 0;//已知dp[0] = 0，加入第0点：(C[0],dp[0]) for(int i = 1; i <= n; ++i){while(l < r && dp[q[l+1]]-dp[q[l]] <= (T[i]+s)*(C[q[l+1]]-C[q[l]]))++l;dp[i] = dp[q[l]]-(T[i]+s)*C[q[l]]+T[i]*C[i]+s*C[n];while(l < r && (dp[i]-dp[q[r]])*(C[q[r]]-C[q[r-1]]) <= (C[i]-C[q[r]])*(dp[q[r]]-dp[q[r-1]]))--r;q[++r] = i;}cout << dp[n];return 0;
}