1063. 任务调度问题

有一个包含 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。显然，不同的块划分方法得到的代价一般是不同的。请编程求出所有块划分方法所能达到的最小代价。