题目
题目描述
$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
输出样例
32
样例说明
在工厂$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}$
代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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}1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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];
}
因为每个元素入队出队次数都是$\Theta \left(1\right)$的，且转移复杂度也是$\Theta \left(1\right)$，所以总复杂度为$\Theta \left(n\right)$。