1063. 任务调度问题

单点时限: 2.0 sec

内存限制: 256 MB

有一个包含 N(N<=10000) 个作业的任务序列需要在一个单处理机上执行。每个作业有它自己的运行时间 Ti 和代价因子 Fi。将序列划分成若干个块来执行,每个块包含若干个序号连续的作业。处理机按照作业序号从小到大开始依次执行各个块,在同一个块里,所有作业的完成时间 Oi 都一样,它们定义为该块开始执行的时刻与块里所有作业的运行时间之和。一个块开始执行之前,需要用长度为 S 的时间进行调整工作。每个作业的代价 Costi 为它的完成时间与代价因子的乘积 Oi * Fi。第一块任务的开始时间为 0。

例如,S=1,有 5 个作业被分成三个块{1,2},{3},{4,5},它的各个参数如表 1-18 所示(其中 T 和 F 为已知,O 和 Cost 是根据分块方法计算出来的)。


作业序号                1           2           3           4           5

T           1       3       4       2       1

F           3       2       3       3       4

O           5       5       10      14      14

Cost            15      10      30      42      56

整个任务的总代价为各个作业的代价之和。在这个例子中,总代价为 153。显然,不同的块划分方法得到的代价一般是不同的。请编程求出所有块划分方法所能达到的最小代价。

输入格式

第一行有两个正整数 N 和 S。(1<=N<=10000,1<=S<=10)

第二行有 N 个正整数,表示 T1,T2......TN, (1<=Ti<=100)

第三行有 N 个整数,表示 F1,F2……FN (1<=Fi<=100)

输出格式

输出一个整数,表示最小的总代价, 我们保证,最后的结果小于 2^64

样例

Input
5 1
1 3 4 2 1
3 2 3 3 4
Output
153

8 人解决,17 人已尝试。

11 份提交通过,共有 74 份提交。

7.5 EMB 奖励。

创建: 18 年,1 月前.

修改: 7 年,3 月前.

最后提交: 1 年,5 月前.

来源: 算法艺术与信息学竞赛

题目标签