[BZOJ 1096][ZJOI 2007]仓库建设【DP+斜率优化+单调队列】

  • 2018-01-27
  • 0
  • 0

Problem:

Time Limit: 10 Sec  Memory Limit: 162 MB

Description

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

Input

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

Output

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

Sample Input

3
0 5 10
5 3 100
9 6 10

Sample Output

32

HINT

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

【数据规模】

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

Source

Solution:

这是一道非常经典的斜率优化 DP

令 dp[i] 表示前 i 个工厂采取某种方案所能达到的最小总费用,则

  • dp[ i ] = min{ dp[ j ] + path_cost[ j + 1 ][ i ] + C[ i ] }
  • 其中 path_cost[ j + 1 ][ i ] = ∑ ( X[ i ] - X[ k ] ) * P[ k ] = X[ i ] * ∑ P[ k ] - ∑ X[ k ] * P[ k ]

我们用 PS[i] 表示 P[i] 的前缀和,XPS[i] 表示 X[i] * P[i] 的前缀和,则原式可化为

  • dp[ i ] = min{ dp[ j ] + X[ i ] * ( PS[ i ] - PS[ j ] ) - XPS[ i ] + XPS[ j ] + C[ i ] }

直接枚举 i, j 复杂度达到 O(N2),TLE 炸飞。。

我们发现 X[i], PS[i], XPS[i] 都是单调的,说不定可以用单调队列斜率优化

决策单调性证明略 ~~ (证明方法详见:[HDU 3507] Print Article【DP+斜率优化+单调队列】

设在状态 i 中,决策 k ( k > j ) 较决策 j 更优,则将两个决策点的比较式转化为斜率式得:

  • ( dp[ k ] - dp[ j ] + XPS[ k ] - XPS[ j ] ) / ( PS[ k ] - PS[ j ] ) ≤ X[ i ]

这样就能将复杂度降到 O(N) 了。

注意如果 X[i] 和 P[i] 都是 int 型的话,在计算 XPS[i] 时两者相乘就可能会溢出

Code: O(N) [40356K, 1684MS]

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

inline void getint(int &num){
	int ch;
	while(!isdigit(ch = getchar()));
	num = ch - '0';
	while(isdigit(ch = getchar())) num = (num << 1) + (num << 3) + ch - '0';
}

int N, X[1000005], P[1000005], C[1000005];
ll PS[1000005], XPS[1000005];
ll dp[1000005];
int q[1000005], fr, re;

inline double Slope(int j, int k){
	return double(dp[k] - dp[j] + XPS[k] - XPS[j]) / double(PS[k] - PS[j]);
}

int main(){
	getint(N);
	for(register int i = 1; i <= N; i++)
		getint(X[i]), getint(P[i]), getint(C[i]);
	for(register int i = 1; i <= N; i++)
		PS[i] = PS[i - 1] + P[i], XPS[i] = XPS[i - 1] + 1LL * X[i] * P[i];  // Beware of overflowing !!!
	fr = re = 0, q[re++] = 0;
	for(register int i = 1; i <= N; i++){
		while(fr + 1 < re && Slope(q[fr], q[fr + 1]) < X[i]) fr++;
		dp[i] = dp[q[fr]] + X[i] * (PS[i] - PS[q[fr]]) - XPS[i] + XPS[q[fr]] + C[i];
		while(fr + 1 < re && Slope(q[re - 1], i) < Slope(q[re - 2], q[re - 1])) re--;
		q[re++] = i;
	}
	printf("%lld\n", dp[N]);
	return 0;
}

评论

还没有任何评论,你来说两句吧



新博客地址:
darkleafin.cf
(该域名已过期且被抢注。。)
darkleafin.github.io


常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
Please refresh the page if the code cannot be displayed normally.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai