[ZJOI2007] 仓库建设

时间：2022-03-28 08:13:18

传送门：>HERE<

题意：有n个地点，每个地点有货物P[i]个，距离起点（地点0）的距离为x[i]。在每个地点建立仓库需要费用c[i]，现在需要在某些地点建设仓库，从而将货物转移到仓库里。规定只能从编号小的地点转移到编号大的地点，同时转移的费用的是路程*货物数量。求最小的总费用（总费用=建设费用+转移费用）

解题思路：

　　动态规划+斜率优化

　　令$f[i]$表示在地点i建设仓库，并且1~i的货物都已经全部处理好了。可以得到$O(n^2)$的状态转移方程$$f[i] = Min\{f[j] + \sum\limits_{k=1}^{i-1}(x[i]-x[k])*p[k] + c[i]\}$$

　　维护前缀和P[i]为数组p的前缀和，g[i]为x[i]*p[i]的前缀和。得到$$f[i] = f[j] + (P[i-1]-P[j])*x[i] - (g[i-1]-g[j]) + c[i]$$

转化为一次函数形式$$f[j]+P[i-1]*x[i]-g[i-1]+g[j]+c[i] = x[i] * P[j] + f[i]            \Longleftrightarrow           y = kx + b$$

去掉没用的项，得$$f[j]+g[j] = x[i] * P[j] + f[i]$$

　　坐标为$(P[j], f[j]+g[j])$

　　正常做就行了

　　这题主要难在f[i]的构想上，斜率优化这一步并没有什么坑点

Code

　　long long

/*By QiXingzhi*/

#include <cstdio>

#include <queue>

#include <cstring>

#include <algorithm>

#define  r  read()

#define  Max(a,b)  (((a)>(b)) ? (a) : (b))

#define  Min(a,b)  (((a)<(b)) ? (a) : (b))

using namespace std;

typedef long long ll;

#define int long long

const int MAXN = ;

const int INF = ;

inline int read(){

    int x = ; int w = ; register int c = getchar();

    while(c ^ '-' && (c < '' || c > '')) c = getchar();

    if(c == '-') w = -, c = getchar();

    while(c >= '' && c <= '') x = (x << ) +(x << ) + c - '', c = getchar();

    return x * w;

}

int n,m,h,t;

int x[MAXN],p[MAXN],c[MAXN],g[MAXN],P[MAXN],q[MAXN],f[MAXN];

inline double X(int i){ return P[i]; }

inline double Y(int i){ return f[i] + g[i]; }

inline double Slope(int i, int j){ return (double)(Y(i)-Y(j)) / (double)(X(i)-X(j)); }

main(){

//    freopen(".in","r",stdin);

    n = r;

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

        x[i] = r, p[i] = r, c[i] = r;

        P[i] = P[i-] + p[i];

        g[i] = g[i-] + x[i] * p[i];

    }

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

        while(h<t && Slope(q[h],q[h+]) < x[i]) ++h;

        f[i] = f[q[h]] + (P[i-]-P[q[h]])*x[i] - g[i-] + g[q[h]] + c[i];

        while(h<t && Slope(q[t-],q[t]) > Slope(q[t],i)) --t;

        q[++t] = i;

    }

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

    return ;

}

相关文章