《P5785 [SDOI2012] 任务安排》

题目描述

机器上有 n 个需要处理的任务，它们构成了一个序列。这些任务被标号为 1 到 n，因此序列的排列为 1,2,3⋯n。这 n 个任务被分成若干批，每批包含相邻的若干任务。从时刻 0 开始，这些任务被分批加工，第 i 个任务单独完成所需的时间是 Ti​。在每批任务开始前，机器需要启动时间 s，而完成这批任务所需的时间是各个任务需要时间的总和。

注意，同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 Ci​。

请确定一个分组方案，使得总费用最小。

输入格式

第一行一个整数 n。 第二行一个整数 s。

接下来 n 行，每行有一对整数，分别为 Ti​ 和 Ci​，表示第 i 个任务单独完成所需的时间是 Ti​ 及其费用系数 Ci​。

输出格式

一行，一个整数，表示最小的总费用。

输入输出样例

输入 #1复制

5 1 1 3 3 2 4 3 2 3 1 4

输出 #1复制

153

说明/提示

对于 100% 数据，1≤n≤3×105，1≤s≤28，∣Ti​∣≤28，0≤Ci​≤28。

代码实现：

#include <iostream> #define int long long using namespace std; const int N = 3e5 + 10; int n, s, T[N], C[N]; int sT[N], sC[N], f[N], q[N], tl = 0; signed main() { cin >> n >> s; for (int i = 1; i <= n; i++) { cin >> T[i] >> C[i]; sT[i] = sT[i - 1] + T[i]; sC[i] = sC[i - 1] + C[i]; } for (int i = 1; i <= n; i++) { int l = 0, r = tl; while (l < r) { int m = (l + r) >> 1; if (f[q[m]] - (s + sT[i]) * sC[q[m]] >= f[q[m + 1]] - (s + sT[i]) * sC[q[m + 1]]) { l = m + 1; } else { r = m; } } f[i] = f[q[r]] + s * (sC[n] - sC[q[r]]) + sT[i] * (sC[i] - sC[q[r]]); while (tl && ((f[i] - f[q[tl]]) * (sC[q[tl]] - sC[q[tl - 1]]) <= (f[q[tl]] - f[q[tl - 1]]) * (sC[i] - sC[q[tl]]))) tl--; tl++; q[tl] = i; } cout << f[n] << endl; return 0; }