【洛谷p2365】任务安排

描述 Description

N个任务排成一个序列在一台机器上等待完成(顺序不得改变),这N个任务被分成若干批,每批包含相邻的若干任务。从时刻0开始,这些任务被分批加工,第i个任务单独完成所需的时间是Ti。在每批任务开始前,机器需要启动时间S,而完成这批任务所需的时间是各个任务需要时间的总和(同一批任务将在同一时刻完成)。每个任务的费用是它的完成时刻乘以一个费用系数Fi。请确定一个分组方案,使得总费用最小。
例如:S=1;T={1,3,4,2,1};F={3,2,3,3,4}。如果分组方案是{1,2}、{3}、{4,5},则完成时间分别为{5,5,10,14,14},费用C={15,10,30,42,56},总费用就是153。

输入格式 Input Format

第一行是N(1<=N<=5000)。
第二行是S(0<=S<=50)。
下面N行每行有一对数,分别为Ti和Fi,均为不大于100的正整数,表示第i个任务单独完成所需的时间是Ti及其费用系数Fi。

输出格式 Output Format

一个数,最小的总费用。

样例输入 Sample Input

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

样例输出 Sample Output

153

题解 Solution

我们用$f[i]$表示从$N$到$i$的最小花费,$F[i],T[i]$是从$N$到$i$的前缀和【$F[i]=F[i+1]+a[i]$】。

得到方程:$f[i]=min{f[j]+(T[i]−T[j]+S)∗F[i]}(i<j<n)$

这样我们可以变形得到:$f[i]=min{f[j]−T[j]∗F[i]}+(T[i]+S)∗F[i]$

对于一个状态$i$我们设$V[j]=f[j]−T[j]∗F[i]$。对于决策$x,y(i<x<y≤n)$,如果$x$比$y$优,即$V(x)<V(y)$,那么$f[x]−T[x]∗F[i]<f[y]−T[y]∗F[i]$

通过变形,我们最终得

$\frac{f[x]−f[y]}{T[x]−T[y]}<F[i]$

我们以$f$为纵坐标,$T$为横坐标,这个就是一个斜率式了。$F[i]$是$i$递减的前缀和,那么$F[i]$随着状态推移会一直增大。那么,如果$x$只要一次比$y$优,以后$x$永远比$y$优。

我们考虑$x,y,z(i<x<y<z≤n)$三个决策,$x$比$y$优即$\frac{f[x]-f[y]}{T[x]-T[y]}<F[i]$,$y$比$z$优$\frac{f[y]-f[z]}{T[y]-T[z]}<F[i]$

因此,当$\frac{f[x]-f[y]}{T[x]-T[y]}<\frac{f[y]-f[z]}{T[y]-T[z]}$时,我们就不需要y了。这也是我们在决策队尾去掉不优于i的判断条件。

Code

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
#include<bits/stdc++.h>
using namespace std;
int t[5010];
int v[5010];
int sumt[5010];
int sumv[5010];
int f[5010];
int n;
int s;
int q[5100];
int head=1;
int tail=0;

double get_k(int x, int y) {
return (1.0 * (f[x] - f[y])) / (1.0 * (sumt[x] - sumt[y]));
}

void solution() {
q[++tail] = 0;
for (int i = n; i >= 1; i--) {
while (head < tail
&& get_k(q[head + 1], q[head]) < sumv[i])
++head;
int j = q[head];
f[i] = f[j] - sumt[j] * sumv[i] + (sumt[i] + s) * sumv[i];
while (head < tail
&& get_k(i, q[tail]) < get_k(q[tail], q[tail - 1]))
--tail;
q[++tail] = i;
}
printf("%d\n", f[1]);
}

int main() {
cin >> n >> s;
for (int i = 1; i <= n; i++)
scanf("%d%d", &t[i], &v[i]);
for (int i = n; i >= 1; i--) {
sumt[i] = sumt[i + 1] + t[i];
sumv[i] = sumv[i + 1] + v[i];
}
solution();
return 0;
}