有 \(n\) 个任务待完成，每个任务有一个完成时间 \(t_i\) 和费用系数 \(f_i\)，相邻的任务可以被分成一批。从零时刻开始这些任务会被机器分批完成，在每批任务开始前机器有一个给定启动时间 \(s\)，一批任务的完成时间是这批任务完成时间之和，同一批任务视作在同一时刻完成。
每个任务的费用是他的完成时刻和费用系数的乘积，请最小化总费用。
分析：如果设 \(dp[i]\) 为第 \(i\) 个任务作为当前这一批任务的最后一个时的最优解，这样会很麻烦，因为会涉及到 "此时一共有多少批" 这个很麻烦的状态。这里有一个dp的trick：费用提前。
我们发现把第 \(i\) 个任务作为当前这一批任务的最后一个时，当前批内以及后面的任务都会多一个 \(s\cdot f_i\) 的费用，于是把 \(dp[i]\) 改为第 \(i\) 个任务作为当前这一批任务的最后一个时，加上后面任务的已有贡献的最优解。可以联系状态转移理解：
\[dp[i]=dp[j]+(\sum_{k=j+1}^if_i\times\sum_{k=1}^it_i)+s\sum_{k=j+1}^nf_i \]