BZOJ1096【ZJOI2007】仓库建设 <斜率优化>

Problem

【ZJOI2007】仓库建设

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

$L$公司有$N$个工厂，由高到底分布在一座山上。如图所示，工厂$1$在山顶，工厂$N$在山脚。由于这座山处于高原内陆地区（干燥少雨），$L$公司一般把产品直接堆放在露天，以节省费用。突然有一天，$L$公司的总裁$L$先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是$L$先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第$i$个工厂目前已有成品$P_i$件，在第$i$个工厂位置建立仓库的费用是$C_i$。对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于$L$公司产品的对外销售处设置在山脚的工厂$N$，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，假设一件产品运送$1$个单位距离的费用是$1$。假设建立的仓库容量都都是足够大的，可以容下所有的产品。你将得到以下数据：

1. 工厂$i$距离工厂$1$的距离$X_i$（其中$X_1=0$）
2. 工厂$i$目前已有成品数量$P_i$
3. 在工厂$i$建立仓库的费用$C_i$

请你帮助$L$公司寻找一个仓库建设的方案，使得总的费用（$建造费用+运输费用$）最小。

Input

第一行包含一个整数$N$，表示工厂的个数。接下来$N$行每行包含两个整数$X_i, P_i, C_i$, 意义如题中所述。

Output

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

Sample Input

3
0 5 10
5 3 100
9 6 10

Sample Output

32

标签：斜率优化DP

Solution

由题意，易得到$DP$方程：$f[i]=c[i]+\min_{j=0}^{i-1}\{f[j]+\sum_{k=j+1}^{i}p[k]\times(x[i]-x[k])\}$
那么对于当前$DP$到的位置$i$，一定存在$p,q\in[0,i)$使得

$$\begin{aligned} f[p]+\sum_{k=p+1}^{i}p[k]\times(x[i]-x[k])&\le f[q]+\sum_{k=q+1}^{i}p[k]\times(x[i]-x[k])\\ f[p]+\sum_{k=p+1}^{i}p[k]\times x[i]-\sum_{k=p+1}^{i}p[k]\times x[k]&\le f[q]+\sum_{k=q+1}^{i}p[k]\times x[i]-\sum_{k=q+1}^{i}p[k]\times x[k]\\ Let\;s_1[i]=\sum_{j=1}^{i}p[j]\times x[j]&,\;s_2[i]=\sum_{j=1}^{i}p[j]\\ f[p]+(s_2[i]-s_2[p])\times x[i]-s_1[i]+s_1[p]&\le f[q]+(s_2[i]-s_2[q])\times x[i]-s_1[i]+s_1[q]\\ f[p]-s_2[p]\times x[i]+s_1[p]&\le f[q]-s_2[q]\times x[i]+s_1[q]\\ \frac{(f[p]-f[q])+(s_1[p]-s_1[q])}{s_2[p]-s_2[q]}&\le x[i]\\ \end{aligned}$$

$$\therefore k(p,q)=\frac{(f[p]-f[q])+(s_1[p]-s_1[q])}{s_2[p]-s_2[q]}\le x[i]\iff p\;is\;better\;than\;q$$

按照此斜率维护单调栈即可。

Code

#include <bits/stdc++.h>
#define MAX_N 1000000
using namespace std;
typedef double dnt;
typedef long long lnt;
template <class T>
inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, c[MAX_N+5], x[MAX_N+5], m[MAX_N+5];
lnt s1[MAX_N+5], s2[MAX_N+5], f[MAX_N+5];    int l, r, sta[MAX_N+5];
dnt calc(int p, int q) {return (dnt)(f[p]-f[q]+s1[p]-s1[q])/(dnt)(s2[p]-s2[q]);}
int main() {
    read(n);
    for (int i = 1; i <= n; i++) read(x[i]), read(m[i]), read(c[i]);
    for (int i = 1; i <= n; i++) s1[i] = s1[i-1]+1LL*m[i]*x[i], s2[i] = s2[i-1]+m[i];
    for (int i = 1; i <= n; i++) {
        while (l < r && calc(sta[l+1], sta[l]) <= x[i]) l++;
        f[i] = f[sta[l]]+1LL*x[i]*(s2[i]-s2[sta[l]])-s1[i]+s1[sta[l]]+c[i];
        while (l < r && calc(sta[r], sta[r-1]) > calc(i, sta[r])) r--;
        sta[++r] = i;
    }
    return printf("%lld", f[n]), 0;
}