P2365 任务安排
对 $t$ 和 $c$ 做前缀和。如果不考虑机器启动时间 $s$ ，则可以显然得到
$$
f _ i = \min _ {j < i} \{f _ j + t _i (c _ i - c _ j) \}
$$
现在考虑 $s$ ，因为决策的不同，不方便将其和 $t$ 算在一起。考虑 $s$ 的贡献，对于一个启动时间，所有还没有完成的物品不论是否将被完成，都需要等待。即
$$
f _ i = \min _ {j < i} \{f _ j + t _i (c _ i - c _ j) + s (c _n - s _j)\}
$$
进一步地，还可以斜率优化，但是此题数据较小，$O(n ^ 2)$ 可以通过。
查看代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| #include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5e3 + 10;
const LL inf = 1e16;
int n;
LL s, t[N], c[N], f[N];
int main()
{
scanf("%d%lld", &n, &s);
for (int i = 1; i <= n; i++)
{
scanf("%lld%lld", &t[i], &c[i]);
t[i] += t[i - 1];
c[i] += c[i - 1];
}
for (int i = 1; i <= n; i++)
f[i] = inf;
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
f[i] = min(f[i], f[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]));
printf("%lld", f[n]);
return 0;
}
|