[SDOI 2012] 任务安排

题目大意

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

$1 \leq N \leq 300,000$

$0 \leq S, F_i \leq 512$

$-512 \leq T_i \leq 512$

题目链接

BZOJ 2726

题解

可写出 DP 方程:

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

以 $sumC(j)$ 为横坐标、$f(j) - S \times sumC(j)$ 为纵坐标,可见答案在一个下凸壳上,目标斜率是 $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;
}