P2365 任务安排
Zirnc
2022-08-20 14:54:56
欢迎访问我的博客：[blog.chungzh.cn](https://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)$
```cpp
#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;
}
```
## 解法三
斜率优化。