题目链接

[ZJOI2007]仓库建设

题目背景

小B的班级数学学到多项式乘法了,于是小B给大家出了个问题:用编程序来解决多项式乘法的问题。

题目描述

L公司有N个工厂,由高到底分布在一座山上。

工厂1在山顶,工厂N在山脚。 由于这座山处于高原内陆地区(干燥少雨),L公司一般把产品直接堆放在露天,以节省费用。

突然有一天,L公司的总裁L先生接到气象部门的电话,被告知三天之后将有一场暴雨,于是L先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。

由于地形的不同,在不同工厂建立仓库的费用可能是不同的。第i个工厂目前已有成品Pi件,在第i个工厂位置建立仓库的费用是Ci。

对于没有建立仓库的工厂,其产品应被运往其他的仓库进行储藏,而由于L公司产品的对外销售处设置在山脚的工厂N,故产品只能往山下运(即只能运往编号更大的工厂的仓库),当然运送产品也是需要费用的,假设一件产品运送1个单位距离的费用是1。

假设建立的仓库容量都都是足够大的,可以容下所有的产品。你将得到以下数据:

  • 工厂i距离工厂1的距离Xi(其中X1=0);
  • 工厂i目前已有成品数量Pi;
  • 在工厂i建立仓库的费用Ci;
    请你帮助L公司寻找一个仓库建设的方案,使得总的费用(建造费用+运输费用)最小。

输入输出格式

输入格式:

第一行包含一个整数N,表示工厂的个数。接下来N行每行包含两个整数Xi, Pi, Ci, 意义如题中所述。

输出格式:

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

输入输出样例

输入样例#1:

3
0 5 10
5 3 100
9 6 10

输出样例#1:

32

说明

在工厂1和工厂3建立仓库,建立费用为10+10=20,运输费用为(9-5)*3 = 12,总费用32。

如果仅在工厂3建立仓库,建立费用为10,运输费用为(9-0)5+(9-5)3=57,总费用67,不如前者优。

对于20%的数据, N ≤500;

对于40%的数据, N ≤10000;

对于100%的数据, N ≤1000000。 所有的Xi, Pi, Ci均在32位带符号整数以内,保证中间计算结果不超过64位带符号整数。

题解

先暂且不看数据的范围,只考虑如何解决题目,很容易可以想到O(n^2)的dp。
dp[i]表示在i这个工厂建立仓库,从工厂1到工厂i所需要的最小费用。
dp的转移方程为$dp[i]=c[i]+min(dp[j]+\sum_{k=j+1}^{i}(p[k](x[i]-x[k])))$
化简后转移方程为$dp[i]=c[i]+min(dp[j]+x[i]
\sum_{k=j+1}^{i}p[k]-\sum_{k=j+1}^{i}(p[k]x[k]))$
但是n的取值范围为1000000,所以n^2的时间复杂度肯定是过不了的,所以这里用斜率优化,把求min的复杂度降低。
因为$\sum_{k=j+1}^{i}p[k]$和$\sum_{k=j+1}^{i}(p[k]
x[k])$中p[]和x[]是输入的信息,可以用前缀和快速求出。
所以我们设S[i]=$\sum_{k=1}^{i}p[k]$,SS[i]=$\sum_{k=1}^{i}(p[k]x[k])$。
所以转移方程变成了$dp[i]=c[i]+min(dp[j]+x[i]
(S[i]-S[j])-(SS[i]-SS[j]))$
我们取$j$,$k$满足 $k<j<i$且$j$比$k$更优,那么有如下不等式:
$c[i]+dp[j]+x[i](S[i]-S[j])-(SS[i]-SS[j])<c[i]+dp[k]+x[i](S[i]-S[k])-(SS[i]-SS[k])$
化简后得到$\frac{(dp[j]+SS[j])-(dp[k]+SS[k])}{S[j]-S[k]}<x[i]$
看到$\frac{(dp[j]+SS[j])-(dp[k]+SS[k])}{S[j]-S[k]}$有没有想到斜率呢?($\frac{x’-x}{y’-y}$)
有了这个不等式后我们就可以利用斜率优化了。
因为斜率要小于x[i]所以我们可以用下凸壳来维护。
没有学习过凸包的同学请先去学习凸包。
上代码:

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
#include<bits/stdc++.h>
using namespace std;
int n;
long long x[1000009],p[1000009],c[1000009];
long long a[1000009],b[1000009],pp[2000009];
long long dp[1000009],l=1,r=1;
double js(int j,int k){
return (1.0*dp[j]-dp[k]+b[j]-b[k])/(a[j]-a[k]);
}
int main(){
scanf("%d",&n);
for(int j=1;j<=n;j++)
scanf("%lld%lld%lld",&x[j],&p[j],&c[j]);
for(int j=1;j<=n;j++)
a[j]=a[j-1]+p[j];
for(int j=1;j<=n;j++)
b[j]=b[j-1]+p[j]*x[j];
for(int j=1;j<=n;j++){
while(l<r && js(pp[l+1],pp[l])<x[j]) l++;//x[j]是单调递增的,所以最佳的答案一定会往后移,从而达到均摊O(1)的复杂度
dp[j]=c[j]+dp[pp[l]]+x[j]*(a[j]-a[pp[l]])-(b[j]-b[pp[l]]);
while(l<r && js(pp[r],pp[r-1])>js(j,pp[r])) r--;//维护下凸壳的性质
pp[++r]=j;
}
printf("%lld",dp[n]);
return 0;
}

最后更新: 2019年09月27日 19:11

原始链接: http://oierlin.cf/2019/07/18/【ZJOI2007】仓库建设/

× 请我吃糖~
打赏二维码