[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;
}
发表评论