题目

题目描述

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

工厂$i$距离工厂$1$的距离$X_{i}$（其中$X_{1}=0$）;
工厂$i$目前已有成品数量$P_{i}$;
在工厂$i$建立仓库的费用$C_{i}$;

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

输入输出格式

输入格式

第一行包含一个整数$N$，表示工厂的个数。接下来$N$行每行包含两个整数$X_{i},P_{i},C_{i}$, 意义如题中所述。

输出格式

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

输入输出样例

输入样例

3
0 5 10
5 3 100
9 6 10

输出样例

样例说明

在工厂$1$和工厂$3$建立仓库，建立费用为$10+10=20$，运输费用为$(9-5)*3=12$，总费用$32$。
如果仅在工厂$3$建立仓库，建立费用为$10$，运输费用为$(9-0)5+(9-5)3=57$，总费用$67$，不如前者优。

数据范围

对于20%的数据， $N \leqslant 500$；
对于40%的数据， $N \leqslant 10000$；
对于100%的数据， $N \leqslant 1000000$。所有的$X_{i},P_{i},C_{i}$均在$32$位带符号整数以内，保证中间计算结果不超过$64$位带符号整数。

题解

首先，这一道题是一道$DP$题，所以，我们先用普通的$DP$做一下这题。
假设$f_{i}$表示工厂$1$到$i$的最小总费用
令$sp_{i}=\sum \limits_{j=1}^{i} p_{j}$，$s_{i}=\sum \limits_{j=1}^{i} s_{j}p_{j}$
由于产品只能往山下运（即只能运往编号更大的工厂的仓库），所以当编号在区间$\left[l,r\right]$中的工厂只有一个仓库（即只有一个仓库在工厂$r$）时，这段区间的费用为$c_{r}+\sum \limits_{i=l}^{r} p_{i} \times \left(x_{r}-x_{i}\right)=c_{r}+x_{r} \times \left(sp_{r}-sp_{l-1}\right)-s_{r}+s_{l-1}$
所以，状态转移方程就是$f_{i}=\min \limits_{0 \leqslant j < i} \left{f_{j}+x_{i} \times \left(sp_{i}-sp_{j}\right)-s_{i}+s_{j}\right}+c_{i}$
最终的结果是$f_{n}$
代码如下：

#include<iostream>
using namespace std;
long long n,x[1000010],c[1000010],p[1000010],sp[1000010],s[1000010],f[1000010];
int main()
{
  cin>>n;
  sp[0]=s[0]=f[0]=0;
  for(int i=1;i<=n;i++){
    cin>>x[i]>>p[i]>>c[i];
    sp[i]=sp[i-1]+p[i],s[i]=s[i-1]+x[i]*p[i];
  }
  for(int i=1;i<=n;i++){
    long long minf=9223372036854775807;
    for(int j=0;j<i;j++) minf=min(minf,f[j]+x[i]*(sp[i]-sp[j])-s[i]+s[j]);
    f[i]=minf+c[i];
  }
  cout<<f[n];
}

这种普通的$DP$的复杂度是$\Theta \left(n^{2}\right)$，只能得到55分，所以，我们需要优化一下程序。
假设我们在计算$f_{i}$，此时有两个决策$a,b$满足$a>b$且$a$比$b$优，即$f_{a}+x_{i} \times \left(sp_{i}-sp_{a}\right)-s_{i}+s_{a}<f_{b}+x_{i} \times \left(sp_{i}-sp_{b}\right)-s_{i}+s_{b}$化简得：
$f_{a}+s_{a}-f_{b}-s_{b}<x_{i} \times \left(sp_{a}+sp_{b}\right)$
$\frac{f_{a}+s_{a}-f_{b}-s_{b}}{sp_{a}+sp_{b}}<x_{i}$
所以我们可以维护一个单调队列，使得从队尾到队首，$\frac{f_{a+1}+s_{a+1}-f_{a}-s_{a}}{sp_{a+1}+sp_{a}}$递减，保证队首决策最优，并每次决策从队首转移即可
代码如下：

#include<iostream>
using namespace std;
long long n,l,r,x[1000010],c[1000010],p[1000010],sp[1000010],s[1000010];
long long f[1000010],q[1000010];
int main()
{
  cin>>n;
    for(int i=1;i<=n;i++){
    cin>>x[i]>>p[i]>>c[i];
    s[i]=s[i-1]+x[i]*p[i],sp[i]=sp[i-1]+p[i];
  }
  for(int i=1;i<=n;i++){
    while(l<r&&f[q[l+1]]+s[q[l+1]]-f[q[l]]-s[q[l]]<x[i]*(sp[q[l+1]]-sp[q[l]])) l++;
    f[i]=f[q[l]]+c[i]+x[i]*(sp[i]-sp[q[l]])-s[i]+s[q[l]];
    while(l<r&&(f[q[r]]+s[q[r]]-f[q[r-1]]-s[q[r-1]])*(sp[i]-sp[q[r]])>(f[i]+s[i]-f[q[r]]-s[q[r]])*(sp[q[r]]-sp[q[r-1]])) r--;
    q[++r]=i;
  }
  cout<<f[n];
}