#211. 任务安排 4
任务安排 4
题目描述
将按顺序排列的 n 个任务分成若干个非空连续批次,不能重排任务。机器从时刻 0 开始。每批先花费启动时间 S,再花费该批所有任务的时间之和;该批所有任务同时在此时完成。任务 i 的费用为它的完成时刻乘以系数 Fi。求所有任务费用和的最小值。
本题是“任务安排”的推广:Ti 和 Fi 均允许为负数,按上述代数定义计算时刻和费用。
输入格式
第一行 n、S。接下来 n 行,每行 Ti、Fi。1≤n≤100000,0≤S≤100,−100≤Ti,Fi≤100。
输出格式
一个整数,表示最小总费用。使用 64 位整数。
示例
2 1
1 2
2 3
19
配套说明
书中本条为理论推广,没有独立在线题号或配套数据。本包明确采用上述输入范围;数据为补生成,答案使用离散 Li Chao 树计算,小规模已与朴素动态规划交叉核对。