「BZOJ1096」[ZJOI2007]仓库建设

Description

nn个工厂,每个工厂只能向编号更大的运输产品。每个工厂运输一件产品一单位距离的费用是11。每个工厂可以花费CiC_i单位修建一个无限容量的仓库,且每个工厂有pip_i个产品。问将所有产品放入仓库的最小费用(建造费用+运输费用)

Input

第一行包含一个整数N,表示工厂的个数。接下来N行每行包含三个整数XiX_i, PiP_i, CiC_i, 意义如题中所述。

Output

仅包含一个整数,为可以找到最优方案的费用。

Solution

斜率优化
可以写出暴力方程:

f[i]=min(f[i],f[j1]+(t[i]t[j1])a[i].x(sum[i]sum[j1])+a[i].c);f[i] = \min(f[i], f[j - 1] + (t[i] - t[j - 1]) * a[i].x - (sum[i] - sum[j - 1]) + a[i].c);

大力
f[i]f[i]ii设立的最优方案。
x[i]<=f[k1]+s[k1](f[j1]+s[j1]t[k1]t[j1]x[i] <= \frac{f[k - 1] + s[k - 1] - (f[j - 1] + s[j - 1] }{t[k - 1] - t[j - 1]}
维护凸包。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<bitset>
#define mk make_pair
#define fi first
#define nd second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 2100000;
struct node {
ll x, p, c;
}a[N];
ll f[N], s[N], t[N];
bool cmp(node x, node y) {
return x.x < y.x;
}
int q[N], head, tail;
int n;
double slop(int x, int y) {
return (double)(f[y - 1] + s[y - 1] - (f[x - 1] + s[x - 1])) / (t[y - 1] - t[x - 1]);
}
int main() {
n = read();
for(int i = 1; i <= n; ++i)
a[i].x = read(), a[i].p = read(), a[i].c = read();
sort(a +1, a + 1 + n, cmp);
for(int i = 1;i <= n; ++i) s[i] = s[i - 1] + a[i].x * a[i].p, t[i] = t[i - 1] + a[i].p;
head = 1;
for(int i = 1; i <= n; ++i) {
while(head < tail && slop(q[tail - 1], q[tail]) >= slop(q[tail - 1], i))--tail;
q[++tail] = i;
while(head < tail && slop(q[head], q[head + 1]) <= a[i].x) ++head;
f[i] = f[q[head] - 1] - t[q[head] - 1] * a[i].x + s[q[head] - 1] + t[i] * a[i].x + a[i].c - s[i];
}
writeln(f[n]);
return 0;
}