[ZJOI2007]仓库建设

Luogu P2120

bzoj 1096

思路

设最后一个选第$i$个工厂建仓库时,对于前$i$个工厂的所有代价和为$f_i$,则可以列得转移方程

$$f_{i}=\min \limits_{0\leq j <i}\{f_j-\sum \limits_{k=j+1}^{i}(P_k\cdot X_k)+X_i\cdot \sum\limits_{k=j+1}^iP_k+C_i\}$$

设$sumW_i=\sum \limits_{j=1}^{i}(P_j\cdot X_j)$,$sumP_i=\sum \limits_{j=1}^iP_j$,则有

$$f_{i}=\min \limits_{0\leq j <i}\{f_j-sumW_i+sumW_j+X_i\cdot(sumP_i-sumP_j)+C_i\}$$

所以当$j_1$比$j_2$转移到$i$更优时,有

$$X_i<\frac{f_{j_2}-f_{j_1}+sumW_{j_2}-sumW_{j_1}}{sumP_{j_2}-sumP_{j_1}}$$

斜率优化一下即可

代码

#include <iostream>
#include <cstdio>

typedef long long LL;

const int MAXN=1e6+10;
int N, X[MAXN], P[MAXN], C[MAXN], q[MAXN];
LL sumP[MAXN], sumW[MAXN], f[MAXN];

int main(){
    scanf("%d", &N);
    for(int i=1; i<=N; i++){
        scanf("%d%d%d", &X[i], &P[i], &C[i]);
        sumP[i]=sumP[i-1]+P[i];
        sumW[i]=sumW[i-1]+(LL)P[i]*X[i];	
    }
    int head=0, tail=0;
    for(int i=1; i<=N; i++){
        while(head<tail && (sumP[q[head+1]]-sumP[q[head]])*X[i]>f[q[head+1]]-f[q[head]]+sumW[q[head+1]]-sumW[q[head]]) head++;
        f[i]=f[q[head]]-sumW[i]+sumW[q[head]]+X[i]*(sumP[i]-sumP[q[head]])+C[i];
        while((sumP[q[tail]]-sumP[q[tail-1]])*(f[i]-f[q[tail]]+sumW[i]-sumW[q[tail]])<(sumP[i]-sumP[q[tail]])*(f[q[tail]]-f[q[tail-1]]+sumW[q[tail]]-sumW[q[tail-1]]) && head<tail) tail--;
        q[++tail]=i;
    }
    printf("%lld", f[N]);
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注