洛谷 P2120 [ZJOI2007]仓库建设 斜率优化

传送~

Description:

有N个工厂,由高到底分布在一座山上.工厂1在山顶,工厂N在山脚.第i个工厂有Pi件产品,在第i个工厂位置建立仓库的费用是Ci.对于没有建立仓库的工厂,要将产品运往山下的仓库(即只能运往编号更大的工厂的仓库).假设一件产品运送1个单位距离的费用是1.

假设建立的仓库容量都都是足够大的,且已知:

工厂i距离工厂1的距离Xi(其中X1=0);

工厂i目前已有成品数量Pi;

在工厂i建立仓库的费用Ci;

求最小费用(建造费用+运输费用)

$n \leq 10^6$ 保证中间结果不超过64位带符号整数.

Solution:

$O(n^3)$

考虑dp.

设$f_i$表示从1(山顶)到i所有产品都运至仓库,且在i建了仓库的最小费用.可以得到如下的转移方程:

对于所有的工厂,显然其产品运往最近的仓库最优.所以对于所有的$j<k\leq i$, 由于$j+1$至$i-1$之间没有仓库,其最优方案即为运往仓库$i$,费用为$(x_i-x_k)\times p_k$.

$O(n^2)$

这样直接转移是$O(n^3)$的.但仔细一想,很容易发现可以把求和公式拆开

我们设$a_i=\sum_{j=1}^i{p_j}, b_i=\sum_{j=1}^i{x_j\times p_j}$,则我们又双叒叕可以把原方程写成

现在显然复杂度降到了$O(n^2)$, 但还是不够,于是斜率优化就要登场了.

$O(n)$

运用套路,我们设$j>k$, 若从$j$转移比$k$更优,则必须满足

很容易发现这是一次函数的点斜式.我们设$slope(j,k)$为上面的左式,即斜率.则当$j>k$且$slope(j,k)<x_i$时,$j$比$k$优.由于$x_i$单调递增,我们可以用单调队列维护斜率,使$slope(i+1, i)$单调递增,且队首最优.

Code

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
#include <bits/stdc++.h>
using namespace std;
template<typename T> inline void read(T& x) {
char ch = getchar(); T a = 0, b = 1;
while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
if (ch == '-') b = -1, ch = getchar();
while (ch >= '0' && ch <= '9') a = (a<<1)+(a<<3)+(ch^48), ch = getchar();
x = a*b;
}
typedef long long ll;
const int maxn = 1e6;
int n, x[maxn+10], p[maxn+10], c[maxn+10], q[maxn+10];
ll f[maxn+10], a[maxn+10], b[maxn+10];
inline double slope(int j, int k) {
return 1.0*(f[j]+b[j]-f[k]-b[k])/(a[j]-a[k]);
}
int main() {
read(n);
for (int i = 1; i <= n; ++i) {
read(x[i]); read(p[i]); read(c[i]);
a[i] = a[i-1]+p[i];
b[i] = b[i-1]+1ll*p[i]*x[i];
}
int l = 1, r = 1;
for (int i = 1; i <= n; ++i) {
while (l < r && slope(q[l+1], q[l]) < x[i]) ++l; //此时q[l]比q[l+1]更劣,由于x[i]递增,故之后一直更劣,弹出
f[i] = f[q[l]]+1ll*x[i]*(a[i]-a[q[l]])-(b[i]-b[q[l]])+c[i];
while (l < r && slope(q[r], q[r-1]) > slope(i, q[r])) --r; //保持队列中斜率单调递增
q[++r] = i;
}
printf("%lld\n", f[n]); //一定记得开longlong
return 0;
}

THANK YOU FOR READING THIS!