朴素 DP:
由于我们需要知道 S 被计算了几次,所以相应的也需要知道这是第几批次的任务。
设 dpi,j 表示分了 i 批次完成前 j 个任务的最小代价。
记 st,sc 分别为 t,c 的前缀和。
则有转移式:
dpi,j=min
注意是 sc_j - sc_k 不是 sc_j - sc_{k-1}。
这样空间是 O(n^2),时间复杂度是 O(n^3)。由于卡空间需要滚动数组优化到 O(n)。
#include <bits/stdc++.h>
using namespace std;
const int N = 5015;
long long INF = 0x3f3f3f3f3f3f3f3f;
int n, S, t[N], c[N];
int st[N], sc[N];
long long dp[2][N];
int main() {
scanf("%d%d", &n, &S);
for (int i = 1; i <= n; i++) scanf("%d%d", &t[i], &c[i]);
for (int i = 1; i <= n; i++) st[i] = st[i - 1] + t[i], sc[i] = sc[i - 1] + c[i];
long long ans = INF;
memset(dp, 0x3f, sizeof dp);
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= n; j++) dp[i & 1][j] = INF;
for (int j = 1; j <= n; j++) {
for (int k = 0; k < j; k++)
dp[i & 1][j] = min(dp[i & 1][j], dp[(i - 1) & 1][k] + (S * 1ll * i + st[j]) * 1ll * (sc[j] - sc[k]));
}
ans = min(ans, dp[i & 1][n]);
}
printf("%lld\n", ans);
return 0;
}
蓝书上介绍了一种费用提前计算的思想。
设 dp_{i} 表示把前 i 个任务分成若干组的最小代价。
发现对于每一组任务,S 的贡献计算是单增的。即 S,2S,3S,\dots,kS。
根据分配律,考虑把代价的计算中 st 和 S 的部分分开来计算。在当前任务提前计算好后面任务中 S 的贡献。
即:
dp_{i} = \min\limits_{0 \leq j \lt i} \{ dp_{j} + (sc_i - sc_j) \times st_i + (sc_n - sc_j) \times S \}
此时空间复杂度是 O(n),时间复杂度 O(n^2),可以通过本题。
#include <bits/stdc++.h>
using namespace std;
const int N = 5015;
long long INF = 0x3f3f3f3f3f3f3f3f;
int n, S, t[N], c[N];
int st[N], sc[N];
long long dp[N];
int main() {
scanf("%d%d", &n, &S);
for (int i = 1; i <= n; i++) scanf("%d%d", &t[i], &c[i]);
for (int i = 1; i <= n; i++) st[i] = st[i - 1] + t[i], sc[i] = sc[i - 1] + c[i];
long long ans = INF;
memset(dp, 0x3f, sizeof dp);
dp[0] = 0;
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
dp[i] = min(dp[i], dp[j] + (sc[i] - sc[j]) * 1ll * st[i] + (sc[n] - sc[j]) * 1ll * S);
printf("%lld\n", dp[n]);
return 0;
}
%%%