由于这三道题都是同一道题，只是数据范围不同，故拉成同一篇博客
题意
有$n$个任务，机器人($jxc$)会把这$n$个任务分成若干批，从时刻$0$开始，任务将被分批加工，执行第$i$个任务需要花费时间为$T_i$。另外，在每一批任务开始前，机器需要$S$的启动时间。
同一批任务将在同一时刻完成。每个任务的费用$=$它完成的时间$\times$一个费用的系数$C_i$。
思路
对于$n \leq 5000$的数据
时间复杂度$O(N^2)$
设$f[i]$表示前$i$个任务所花费最小价值。
初始化：
$$f[i]=inf|1<=i<=n,f[0]=0$$
转移方程：
$$f[i]=min \left{f[j-1]+S(c[n]-c[j-1])+t[i](c[i]-c[j-1])|1<=j<=i \right}$$
1 | #include<bits/stdc++.h> |
对于$1\leq N \leq 10^4$的数据
时间复杂度约为$O(N)$
转移方程同上，
$$f[i]=min \left{ f[j-1]+S(c[n]-c[j-1])+t[i](c[i]-c[j-1])|1<=j<=i \right }$$
将只含有$i$的项移出，得：
$$f[i]=min \left { f[j-1]-Sc[j-1]-t[i]c[j-1]|1<=j<=i \right }+Sc[n]+t[i]c[i]$$
合并同类项，得：
$$f[i]=min \left { f[j]-(S+t[i])c[j]|0<=j<=i-1 \right }+Sc[n]+t[i]*c[i]$$
设$y=f[j]$,$k=S+t[i]$,$x=c[j]$,$b=Sc[n]+t[i]c[i]$
那么：
$$f[i]=y-kx+b$$
即：
$$y=kx+(f[i]-b)$$
斜率优化一：
因为$t[i]$在递增，斜率$k$在变大，直线越来越陡，所以队首的两个点之间斜率至少要大于$(S+t[i])$。
即：$(f[q[l+1]]-f[q[l]])/(c[q[l+1]]-c[q[l]])>(S+t[i])$
即：若$(f[q[l+1]]-f[q[l]])/(c[q[l+1]]-c[q[l]])<=(S+t[i])$，队首弹出
化简，得：若$(f[q[l+1]]-f[q[l]])<=(S+t[i])*(c[q[l+1]]-c[q[l]])$，队首弹出斜率优化二：
确保右侧的斜率大于左侧的斜率，即：$(f[q[r]]-f[q[r-1]])/(c[q[r]]-c[q[r-1]])<(f[i]-f[q[r]])/(c[i]-c[q[r]])$。
若$(f[q[r]]-f[q[r-1]])/(c[q[r]]-c[q[r-1]])>=(f[i]-f[q[r]])/(c[i]-c[q[r]])$,队尾弹出。
化简，得：若$(f[i]-f[q[r]])(c[q[r]]-c[q[r-1]])<=(f[q[r]]-f[q[r-1]])(c[i]-c[q[r]])$，队尾弹出
1 | #include<bits/stdc++.h> |
对于$1 \leq N \leq 3 \times 10^5 , \left| T_i \right|<2^8$的数据
虽然添加了单调队列的优化，但是时间可以为负数，所以之前维护的单调性就不存在了，所以我们需要使用二分+单调队列来维护斜率。
1 | #include<bits/stdc++.h> |
