欢迎访问我的博客：blog.chungzh.cn

摘自《进阶指南》。

解法一

求出 $t, f$ 的前缀和 $sumt, sumf$。设 $F(i, j)$ 表示把前 $i$ 个任务分成 $j$ 批执行的最小费用。状态转移方程为：

$$ F(i, j) = min_{0<=k<i}\{F(k, j-1)+(S\times j+sumt[i])\times(sumf[i]-sumf[k])\} $$

时间复杂度为 $O(N^3)$

解法二

上一个解法中需要批数 $j$ 是因为我们需要知道机器启动了多少次（每次启动都需要 $S$ 单位时间），才能知道当前这批任务的完成时刻。

事实上，机器因为执行这批任务而花费的启动时间 $S$，会累加到在此之后所有任务的完成时间。设 $F(i)$ 表示把前 $i$ 个任务分成若干批执行的最小费用，状态转移方程为：

$$ F(i)=min_{0<=j<i}\{F(j)+sumt[i]\times (sumf[i]-sumf[j])+S\times (sumf[N]-sumf[j])\} $$

在上式中，$sumt[i]$ 是忽略机器启动时间时，这批任务的完成时刻。因为这批任务的执行，机器的启动时间 $S$ 会对第 $j+1$ 个之后的所有任务产生影响，就把这部分补充到费用中。

通过这样，我们就不需要知道之前启动了多少次也可以计算出费用了。

这种思想叫做 费用提前计算。

时间复杂度为 $O(N^2)$

#include <algorithm>
#include <cmath>
#include <deque>
#include <iostream>
using namespace std;
const int MAXN = 5005;
int n, s;
long long f[MAXN], sumt[MAXN], sumc[MAXN];
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> s;
  for (int i = 1; i <= n; i++) {
    int t, c;
    cin >> t >> c;
    sumt[i] = sumt[i - 1] + t;
    sumc[i] = sumc[i - 1] + c;
  }
  memset(f, 0x3f, sizeof f);
  f[0] = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j < i; j++) {
      f[i] = min(f[i], f[j] + sumt[i] * (sumc[i] - sumc[j]) + s * (sumc[n] - sumc[j]));
    }
  }
  cout << f[n] << endl;
  return 0;
}

解法三

斜率优化。