[SDOI 2012] 任务安排

题目大意

机器上有 NN 个需要处理的任务,它们构成了一个序列,标号为 11NN。这 NN 个任务被分成若干批,每批包含相邻的若干任务。从时刻 00 开始,这些任务被分批加工,第 ii 个任务单独完成所需的时间是 TiT_i。在每批任务开始前,机器需要启动时间 SS,而完成这批任务所需的时间是各个任务需要时间的总和,同一批任务将在同一时刻完成。每个任务的费用是它的完成时刻乘以一个费用系数 FiF_i。最小化总费用。

1N300,0001 \leq N \leq 300,000

0S,Fi5120 \leq S, F_i \leq 512

512Ti512-512 \leq T_i \leq 512

题目链接

【SDOI 2012】任务安排 - Luogu 5785

题解

可写出 DP 方程:

\begin{align} f(i) &= \min_\limits{0 \leq j < i}(f(j) + (sumC(i) - sumC(j)) \times sumT(i) + (sumC(n) - sumC(j)) \times S) \\ &= sumC(i) \times sumT(i) + S \times sumC(n) + \min_\limits{0 \leq j < i}(f(j) - sumC(j) \times (sumT(i) + S)) \end{align}

对于决策点 a,ba, b (a<b)(a < b),假设 aa 更优,有:

\begin{align} f(a) - sumC(a) \times (sumT(i) + S) &< f(b) - sumC(b) \times (sumT(i) + S) \\ \frac{(f(a) - S \times sumC(a)) - (f(b) - S \times sumC(b))}{sumC(a) - sumC(b)} &< sumT(i) \end{align}

sumC(j)sumC(j) 为横坐标、f(j)S×sumC(j)f(j) - S \times sumC(j) 为纵坐标,可见答案在一个下凸壳上,目标斜率是 sumT(i)sumT(i)

横坐标递增,可以用单调队列维护上凸壳;目标斜率不单调,需要用二分查找决策点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <cstdio>

const int MAXN = 300005;

long long sumT[MAXN], sumC[MAXN], f[MAXN], S;

long long y(int x) {
return f[x] - S * sumC[x];
}

int bisearch(long long k, int *l, int *r) {
while (l < r) {
int *mid = l + ((r - l) >> 1);
if ((y(*(mid + 1)) - y(*mid)) <= k * (sumC[*(mid + 1)] - sumC[*mid])) l = mid + 1;
else r = mid;
}
return *l;
}

void dp(int n) {
static int q[MAXN];
int *l = q, *r = q;

for (int i = 1; i <= n; i++) {
int j = bisearch(sumT[i], l, r);
f[i] = f[j] + sumT[i] * (sumC[i] - sumC[j]) + S * (sumC[n] - sumC[j]);
while (l < r && (long double) (y(*r) - y(*(r - 1))) * (sumC[i] - sumC[*r])
>= (long double) (y(i) - y(*r)) * (sumC[*r] - sumC[*(r - 1)])) --r;
*++r = i;
}
}

int main() {
int n;
scanf("%d %lld", &n, &S);
for (int i = 1; i <= n; i++) scanf("%lld %lld", &sumT[i], &sumC[i]);
for (int i = 2; i <= n; i++) {
sumT[i] += sumT[i - 1];
sumC[i] += sumC[i - 1];
}

dp(n);
printf("%lld\n", f[n]);

return 0;
}