[BZOJ 1096][ZJOI 2007]仓库建设【DP+斜率优化+单调队列】
Problem:
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
0 5 10
5 3 100
9 6 10
Sample Output
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; }
发表评论