ZJOI2007 仓库建设

发表于 | 分类于

ZJOI2007 仓库建设

题目

题目描述

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 ≤500$；
对于$40%$的数据，$ N ≤10000$；
对于$100%$的数据，$ N ≤1000000$。
所有的$X_i, P_i, C_i$均在$32$位带符号整数以内，保证中间计算结果不超过$64$位带符号整数。

题解

分析

解决最优化问题，显然是DP

状态设计

首先来设计一个状态
$$f[i],i∈[1，n]$$
表示在第$i$个工厂建设仓库,并将其上面的所有库存解决的最小花费，这么设计状态的好处是最下面的工厂是一定要建设仓库的，所以$f[n]$就是答案。

状态转移方程

显然在第$i$个工厂建立仓库，就要由向下运输货物的起点转移过来，于是有：
$$f[i]=min(f[j]+w(j,i)+c[i]),j\in[1,j)$$

其中$w(i,j)$表示将$i+1…j-1$的货物都转移到$i$的费用。

$O(n^3)$

枚举$i,j$，对于每个$(i,j)$,分别去计算$w(i,j)$，显然算法时间复杂度是$O(n^3)$

code

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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+1e3;
int n,x[N],p[N],c[N],f[N],ans;
int w(int i,int j)
{
    int ret=0;
    for(int k=i+1;k<j;k++)
        ret+=(x[j]-x[k])*p[k];
    return ret;
}
int main()
{
//	freopen("storage.in","r",stdin);
//	freopen("storage.out","w",stdout);
    memset(f,0x3f,sizeof(f));
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d%d",&x[i],&p[i],&c[i]);
    f[0]=0;
    for(int i=1;i<=n;i++)
        for(int j=0;j<i;j++)
            f[i]=min(f[i],f[j]+w(j,i)+c[i]);
    printf("%d",f[n]);
}

对于原题数据，显然本算法只有20分，但是由于时间是3s，且cogs开启了O2优化，水到了30分。

$O(n^2)$

通过观察可以发现，对于每次循环的$i,j$，$w(i,j)$中变量$i$是一个定值，做了大量重复计算，我们可以通过前缀和的思想，通过后缀和来计算$w(i,j)$，但是由于空间问题$O(n^2)$的空间不被接受，于是采用滚动数组实现。

$w[j]$计算递推式如下：
$$w[j]=w[j+1]+(x[i]-x[j])*p[j]$$

code

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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=1e6+1e3;
long long n,x[N],p[N],c[N],f[N],ans,w[N];
int main()
{
    //freopen("storage.in","r",stdin);
    //freopen("storage.out","w",stdout);
    memset(f,0x3f,sizeof(f));
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld%lld",&x[i],&p[i],&c[i]);
    f[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=i-1;j>=1;j--)
            w[j]=w[j+1]+(x[i]-x[j])*p[j];
        for(int j=0;j<i;j++)
            f[i]=min(f[i],f[j]+w[j+1]+c[i]);
    }
    printf("%lld",f[n]);
}

同样的好运气，水到了50分。。。

$O(n)$

本题的数据显然是接近线性的算法，我们并没有对最初始的式子进行任何的变形，现在对其进行一个展开。
$$f[i]=min(f[j]+w(j,i)+c[i]),j\in[1,j)$$
$$==>$$
$$f[i]=min(f[j]+\sum_{k=j+1}^i(x[k]-x[j])×p[k]+c[i])$$

对中间求和部分展开得：

$$\sum_{k=j+1}^i(x[i]-x[k])×p[k]$$
$$=(x[i]-x[j+1])×p[j+1]+(x[i]-x[j+2])×p[j+2]$$
$$+…+(x[i]-x[i-1])×p[i-1]+(x[i]-x[i])×p[i])$$
$$=x[i]×(p[j+1]+…+p[i])-$$
$$(x[j+1]×p[j+1]+…+x[i]×p[i])$$

不妨设

$sump(i)=p[1]+…+p[i]$

$sumx(i)=x[1]×p[i]+…+x[i]×p[i]$

则
$$f[i]=min(f[j]+x[i]×(sump(i)-sump(j))-$$
$$(sumx(i)-sumx(j))+c[i])$$

将与$j$无关的式子提出来之后

得到函数$f’(i)=min(f(j)-x[i]×sump(j)+sumx(i))$

使得$f’(i)$有最小值即可

令$a[i]=-x[i],x’[j]=sump[j],y’[j]=f[j]+sumx[j]$

带入得

$$f’(i)=min(a[i]*x’[j]+y[j])$$

则求

最小的$(x’,y’)$使得$f’(i)$最小

则

$$y’[j]=a[i]*x’[j]-f’[i]$$
使得$a[i]$最大就可以了

维护一个下凸的函数图像

$$k= \frac{f[i]+sumx[i]-f[j]-sumx[j]}{sump[i]-sump[j]}$$

则

$$k<x[j]$$
单调队列维护即可

code

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
#include <cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define N 1000500
long long int f[N],x[N],c[N],sumx[N],sump[N],p[N],q[N]; 
long long int calf(int i,int j) 
{
    return f[i]+sumx[i]-f[j]-sumx[j];
}
int main()
{
//	freopen("storage.in","r",stdin);
//	freopen("storage.out","w",stdout);
    int i,j,n;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld",&x[i],&p[i],&c[i]);
        sumx[i]=sumx[i-1]+x[i]*p[i];
        sump[i]=sump[i-1]+p[i];
    }
    int head=0,tail=1;
    for(i=1;i<=n;i++)
    {
        while(head<tail&&calf(q[head+1],q[head])<x[i]*(sump[q[head+1]]-sump[q[head]])) 
            head++; 
        f[i]=f[q[head]]+sumx[q[head]]-x[i]*sump[q[head]]+x[i]*sump[i]-sumx[i]+c[i];
        while(head<tail&&calf(q[tail],i)*(sump[q[tail-1]]-sump[q[tail]])<=calf(q[tail-1],q[tail])*(sump[q[tail]]-sump[i])) 
            tail--;//避免了实数型的使用，加快了速度 
        q[++tail]=i; 
    }
    printf("%lld\n",f[n]);
    return 0;
}