[ZJOI 2007] 仓库建设

题目大意

nn 个工厂,每个工厂距工厂 11 的距离为 xix_i(递增),有产品 pip_i 个,建立仓库的费用为 cic_i。现建设一些仓库,每个工厂的产品只能向编号更大的仓库运送,费用为产品数 ×\times 距离。求把所有产品运送到仓库的最小费用。

1n1,000,0001 \leqslant n \leqslant 1,000,000

xix_ipip_icic_i均在 int

题目链接

【ZJOI 2007】仓库建设 - Luogu 2120

题解

DP + 斜率优化。

f[i]f[i] 表示前 ii 个仓库的答案,转移为:

\begin{align} f[i] &= min(f[j] + c[i] + \sum_{k = j + 1}^{i} p[k] \times (x[i] - x[k]) \quad j \in [1, \; i - 1] \\ &= min(f[j] + c[i] + (P[i] - P[j]) \times x[i] - (XP[i] - XP[j])) \end{align}

其中 PPpip_i 的前缀和,XPXPxi×pix_i \times p_i 的前缀和。

对于后面的一堆,考虑两个决策点 aabba>ba > b),假设 aa 优于 bb,有:

\begin{align} f[a] + c[i] + (P[i] - P[a]) \times x[i] - (XP[i] - XP[a]) &< f[b] + c[i] + (P[i] - P[b]) \times x[i] \\ & - (XP[i] - XP[b]) \\ f[a] - P[a] \times x[i] + XP[a] &< f[b] - P[b] \times x[i] + XP[b] \\ \frac{(f[a] + XP[a]) - (f[b] + XP[b])}{P[a] - P[b]} &< x[i] \end{align}

用斜率的单调队列维护决策点,最优决策点在一个下凸包上。

代码

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
26
27
28
29
30
31
32
33
34
#include <cstdio>
const int MAXN = 1000005;
long long f[MAXN];
long long p[MAXN], x[MAXN], c[MAXN];
long long pSumP[MAXN], pSumXP[MAXN];
long long y(int i) {
return f[i] + pSumXP[i];
}
double slope(int i, int j) {
return (double) (y(i) - y(j)) / (pSumP[i] - pSumP[j]);
}
int n;
void dp() {
static int q[MAXN];
int *l = q, *r = q;
for (int i = 1; i <= n; i++) {
while (l < r && slope(*l, *(l + 1)) < x[i]) l++;
int k = *l;
f[i] = f[k] + (pSumP[i] - pSumP[k]) * x[i] - (pSumXP[i] - pSumXP[k]) + c[i];
while (l < r && slope(*(r - 1), *r) > slope(*r, i)) r--;
*++r = i;
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%lld %lld %lld", &x[i], &p[i], &c[i]);
for (int i = 1; i <= n; i++) {
pSumP[i] = pSumP[i - 1] + p[i];
pSumXP[i] = pSumXP[i - 1] + x[i] * p[i];
}
dp();
printf("%lld\n", f[n]);
return 0;
}