解法一  时间复杂度$O(N^3)$  期望得分：$60$

1、求出 $T,C$ 的前缀和$sumT[i]$和$sumC[i]$;

2、设$f(i,j)$表示：把前 $i$ 个任务分成 $j$ 批执行的最小费用;

3、以第 $j-1$ 批和第 $j$ 批任务的分界点为$DP$的“$决策$”，状态转移方程为：

$f(i,j) = min\{ f(k,j-1) + (S*j + sumT[i]) * (sumC[i]-sumC[k]) \} (0<=k<j)$

其中，$(S*j + sumT[i])$为第 $j$ 批任务完成的时间，$(sumC[i]-sumC[k])$为第 $j$ 批（$[k+1,i]$）任务的费用系数之和。

解法二  时间复杂度:$O(N^2)$  期望得分：$100$

本题并没有规定把任务分成多少批，解法$1$之所以需要批次 $j$ ,是因为需要知道机器启动了多少次(每次需要启动时间$S$),从而计算出任务 $i$ 所在批次的完成时刻。

事实上，执行一批任务时，不容易直接得知此前机器启动了几次。但我们知道，机器因执行该批次而花费的时间 $S$，会累加到之后所有任务的完成时刻上。

设：$f(i)$ 表示把前 $i$ 个任务分成若干批执行的最小费用，状态转移方程为：

$f(i) = min\{ f(j) + sumT[i] * (sumC[i]-sumC[j]) + S*(sumC[N]-sumC[j]) \} (0<=j<j)$

在上式中，$[j+1,i]$范围内的任务在同一批完成，$sumT[i]$是忽略机器启动时间时，该批任务的完成时刻。

因为该批任务的执行，机器的启动时间 $S$ 会对第 $j+1$ 个之后的所有任务产生影响，故我们需要把这部分补充到费用中。

也就是说，我们没有直接求出每批任务的完成时刻，而是在一批任务“开始”对后续任务产生影响时，就先把费用累加到答案中。这是一种名为“费用提前计算”的经典思想。

题解来自《算法竞赛进阶指南》$P322$