关注 洛谷 谢谢喵~
博客园 使用更佳~~~
正文
先看例题理解。
任务安排
O(N2)O(N^2)O(N2) DP
设 dpidp_idpi 表示前 iii 个物品被分批后的最小总费用，同时处理开机时间 sss 对后面状态的影响，则有转移 dpi=minj=0i−1dpj+∑k=1itk×∑k=j+1ifk+s×∑k=j+1nfkdp_i=\min_{j=0}^{i-1} dp_j + \sum_{k=1}^i t_k \times \sum_{k=j+1}^i f_k + s \times \sum_{k=j+1}^n f_kdpi =minj=0i−1 dpj +∑k=1i tk ×∑k=j+1i fk +s×∑k=j+1n fk
，显然可以预处理出来前缀和求解，变为：dpi=minj=0i−1dpj+ti×(fi−fj)+s×(fn−fj)dp_i = \min_{j=0}^{i-1} dp_j + t_i \times (f_i-f_j)+ s \times (f_n -f_{j})dpi =minj=0i−1 dpj +ti ×(fi −fj )+s×(fn −fj )。
时间复杂度 O(n2)O(n^2)O(n2)。
O(NLOGN)O(N \LOG N)O(NLOGN) DP
题目链接
将原先的式子变形：
dpi=minj=0i−1dpj+ti×fi−ti×fj+s×fn−s×fj=ti×fi+s×fn+minj=0i−1dpj−s×fj−ti×fj\begin{aligned} dp_i&=\min_{j=0}^{i-1} dp_j + t_i \times f_i - t_i \times f_j + s \times f_n -s \times f_j\\&= t_i \times f_i+s \times f_n + \min_{j=0}^{i-1} dp_j-s \times f_j - t_i\times f_j \end{aligned} dpi =j=0mini−1 dpj
+ti ×fi −ti ×fj +s×fn −s×fj =ti ×fi +s×fn +j=0mini−1 dpj −s×fj −ti ×fj
考虑对于 j>j1j>j1j>j1，什么时候 jjj 不优于 j1j1j1。
dpj−s×fj−ti×fj≥dpj1−s×fj1−ti×fj1dpj−dpj1≥s×(fj−fj1)+ti×(fj−fj1)dpj−dpj1≥(s+ti)×(fj−fj1)dpj−dpj1fj−fj1≥s+ti\begin{aligned} dp_j - s\times f_j - t_i \times f_j &\ge dp_{j1} - s\times f_{j1} - t_i \times f_{j1}\\ dp_j - dp_{j1} &\ge s \times (f_{j}-f_{j1}) + t_i \times (f_{j}-f_{j1}) \\ dp_j-dp_{j1}
&\ge (s+t_i) \times (f_j-f_{j1}) \\ \dfrac{dp_j - dp_{j1}}{f_j -f_{j1}} &\ge s+t_i \end{aligned} dpj −s×fj −ti ×fj dpj −dpj1 dpj −dpj1 fj −fj1 dpj −dpj1 ≥dpj1 −s×fj1 −ti ×fj1 ≥s×(fj −fj1 )+ti ×(fj −fj1 )≥(s+ti )×(fj −fj1 )≥s+ti
发现这个东西很像斜率表达式，那不妨设 yi=dpi,xi=fiy_i = dp_i,x_i=f_iyi =dpi ,xi =fi ，则原式要求即为 (xj1,yj1)(x_{j1},y_{j1})(xj1 ,yj1 ) 与 (xj,yj)(x_{j},y_{j})(xj ,yj ) 之间直线的斜率大于等于 s+tis+t_is+ti 。
接下来看一张图：
设 AC,CBAC,CBAC,CB 斜率分别为 k1,k2k1,k2k1,k2，s−tis-t_is−ti 为 k0k0k0。首先有 k1>k2k1>k2k1>k2，然后根据我们刚才的证明，有若 k1≤k0k1\le k0k1≤k0，则 CCC 点优于 AAA 点，反之亦然；若 k2≤k0k2 \le k0k2≤k0，则 BBB 点优于 CCC 点，反之亦然。
则现在有三种情况：
* k0≤k2<k1k0 \le k2 < k1k0≤k2<k1，则 CCC 不优于 AAA 点。
* k2≤k0≤k1k2 \le k0 \le k1k2≤k0≤k1，则 CCC 不优于 BBB 点。
* k2<k1≤k0k2 < k1 \le k0k2<k1≤k0，则 CCC 既不优于 AAA 也不优于 BBB。
综上，上述情况下，CCC 一定会被踢出决策候选点，所以最后是一个下凸包的结构。
现在只剩下两个关键问题：如何维护下凸包和对于每个 iii 如何找到答案。
维护凸壳可以使用单调队列维护，队列中始终保持一个凸包的形状，那么每加入一个，只需找到相邻的两个点，并判断他们的斜率关系即可，注意要一直弹出队头（尾），知道剩下的图形是一个凸包。因为每新加入一个点，可能需要删除多个点才可以变为一个凸包。
那么对于每个 iii 如何找到答案呢？考虑之前证明出第 jjj 个点与第 j1(j<j1)j1(j<j1)j1(j<j1) 个点连线的斜率大于等于 s+tis+t_is+ti 时，第 jjj 个点更优，又因为凸壳斜率单增，所以只需要二分找到第一个大于等于 s+tis+t_is+ti 的点即可。
时间复杂度 O(nlogn)O(n \log n)O(nlogn)。
O(N)O(N)O(N) DP
发现凸包单增，s+tis+t_is+ti 单增，则维护指针记录即可。
加强版
此时发现 s+tis+t_is+ti 并不具备单调性，那么此时直接二分即可。
