P2120 [ZJOI2007] 仓库建设（斜率优化DP)

题意：\(1\sim N\) 号工厂，第\(i\) 个工厂有\(P_i\)个成品，第\(i\)个工厂建立仓库需要\(C_i\)的费用，该工厂距离第一个工厂的距离为\(X_i\)，编号小的工厂只能往编号大的工厂搬用成品，每单位成品搬每单位距离需要花费1，问所有成品搬到工厂里面所需的最少费用是多少

分析

设\(f[i]\) 为第 i 个工厂建立仓库，前 i 个工厂的成品都搬到仓库中的最小花费，则容易得到动态转移方程:

\[f[i] = min(f[j] + P_{j+1}(X_i-X_{j+1}) + P_{j+2}(X_i-X_{j+2})+\cdots + P_{i-1}(X_i-X_{i-1}))+C_i
\]

通式为

\[f[i]=min(f[j]+\sum_{k=j+1}^{i-1}P_k\cdot X_i-\sum_{k=j+1}^{i-1}P_k\cdot X_k)+C_i
\]

令 \(s[i] = \sum_1^i P[i], ~~g[i] = \sum_1^iP_i\cdot X_i\),

则方程变为

\[f[i] = min(f[j] + X_i\cdot (s[i-1]-s[j])-(g[i-1]-g[j]))+C_i
\]

则对于最优决策 \(j\) ，有

\[f[j]+g[j]=X_i\cdot s[j]+f[i]-X_i\cdot s[i-1]-C_i
\]

也就是要找 \(y = kx+b\)，\(k\)已知，找一对\(x,y\)使得截距最小

由于\(X[i]\)是随\(i\)递增的，所以要维护的决策集的斜率也是递增的

#include <bits/stdc++.h>

using namespace std;

const int N = 1e6+10;

typedef long long ll;

ll C[N],P[N],X[N],f[N],s[N],g[N];

int n;

int q[N],l,r;

long double slope(int i,int j){

    return (long double)((f[i]+g[i]) - (f[j]+g[j]))/(s[i]-s[j]);

}

int main(){

    scanf("%d",&n);

    for(int i=1;i<=n;i++){

        scanf("%lld%lld%lld",&X[i],&P[i],&C[i]);

        s[i] = s[i-1] + P[i];

        g[i] = g[i-1] + P[i] * X[i];

    }

    l = r = 0;

    for(int i=1;i<=n;i++){

        while(l < r && slope(q[l],q[l+1]) <= X[i])l++;

        int j = q[l];

        f[i] = f[j] + (s[i-1] - s[j]) * X[i] - g[i-1] + g[j] + C[i];

        while(l < r && slope(q[r-1],q[r]) > slope(q[r-1],i))r--;

        q[++r] = i;

    }

    printf("%lld\n",f[n]);

    return 0;

}

巴特西

P2120 [ZJOI2007] 仓库建设（斜率优化DP)

最新文章

热门文章