题目描述
nnn 个任务排成一个序列在一台机器上等待完成（顺序不得改变），这 nnn 个任务被分成若干批，每批包含相邻的若干任务。
从零时刻开始，这些任务被分批加工，第 iii 个任务单独完成所需的时间为 tit_iti。在每批任务开始前，机器需要启动时间 sss，而完成这批任务所需的时间是各个任务需要时间的总和（同一批任务将在同一时刻完成）。
每个任务的费用是它的完成时刻乘以一个费用系数 fif_ifi。请确定一个分组方案，使得总费用最小。
输入格式
第一行一个正整数 nnn。
第二行是一个整数 sss。下面 nnn 行每行有一对数，分别为 tit_iti 和 fif_ifi，表示第 iii 个任务单独完成所需的时间是 tit_iti 及其费用系数 fif_ifi。
输出格式
一个数，最小的总费用。
输入输出样例
输入 #1
5 1 1 3 3 2 4 3 2 3 1 4输出 #1
153说明/提示
【数据范围】
对于 100%100%100% 的数据，1≤n≤50001\le n \le 50001≤n≤5000，0≤s≤500 \le s \le 500≤s≤50，1≤ti,fi≤1001\le t_i,f_i \le 1001≤ti?,fi?≤100。【样例解释】
如果分组方案是 {1,2},{3},{4,5}{1,2},{3},{4,5}{1,2},{3},{4,5}，则完成时间分别为 {5,5,10,14,14}{5,5,10,14,14}{5,5,10,14,14}，费用 C=15+10+30+42+56C=15+10+30+42+56C=15+10+30+42+56，总费用就是 153153153。
将前\(i\)个任务分成\(j\)次的花费：
需要知道机器启动了多少次
费用提前计算：
当我们的目标是求最小截距的时候，想象为一条线从下往上平移，第一次接触到的点截距最小。我们要寻找这个“最下面的”点，需要维护下凸包，通过斜率来判断点。
因为\(k = t[i] + s\)具有单调性，也就是说那条从下往上平移的线的斜率随着\(i\)的递推是逐渐增大的，而我们要寻找的那个”最下面“的点的横坐标也一定是随着\(i\)的地推逐渐增大的，为了及时排除无用状态，使用一个队列。
初始化：que[0] = 0
添加新的决策集：将\((f[i], pay[i])\)入队并不断判断队尾三个元素的凸包性质，即若不满足三个点连出的两条线的斜率递增，则删除中间点。
#include<map>
#include<queue>
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
int n, s, tt, ff;
ll pay[300010], t[300010], f[300010];
double slope(int a, int b){
return 1.0 * (pay[b] - pay[a]) / (f[b] - f[a]);
}
int que[300010];
int h, tail;
int main(){
scanf("%d%d", &n, &s);
for(int i = 1; i <= n; i++){
scanf("%d%d", &tt, &ff);
t[i] = t[i - 1] + tt;
f[i] = f[i - 1] + ff;
}
h = tail = 1;
que[1] = 0;
for(int i = 1; i <= n; i++){
while(h < tail && pay[que[h + 1]] - pay[que[h]] < (t[i] + s) * (f[que[h + 1]] - f[que[h]])) h++;
pay[i] = pay[que[h]] + s * (f[n] - f[que[h]]) + t[i] * (f[i] - f[que[h]]);
while(h < tail && (pay[que[tail]] - pay[que[tail - 1]]) * (f[i] - f[que[tail]]) > (pay[i] - pay[que[tail]]) * (f[que[tail]] - f[que[tail - 1]])) tail--;
que[++tail] = i;
}
printf("%lld\n", pay[n]);
return 0;
}
原文：https://www.cnblogs.com/ZhengkunJia/p/13639903.html