BZOJ 1096/3437/3156: [ZJOI2007]仓库建设 – [DP/斜率优化]


题目传送门(BZOJ)
>原文链接<

题解 :

三倍经验

本题Dp的方程比较好推导,我们设两个数组,sum对货物量进行前缀求和、sum1对前i-1个仓库的货物都运到i的代价进行求和

F[i]为在i点建仓库的总最小花费。

那么DP方程显然为F[i]=\min{ f[j] + sum1[i] – sum1[j] – sum[j] \times(x[i] – x[j]) + c[i]}

考虑斜率优化 。 对上式进行化简得

F[i]-c[i] – sum1[i] = F[j] – sum1[j] – sum[j] \times x[j] + s[j] \times x[i]

我们设

B(j) = F[j] + x[j] \times s[j] -sum1[j]

K(j)= -sum[j]

Y(i,j)= K(j)\times x[i] + B(j) = F[i] – c[i] – sum1[i]

F[i] = Y(i,j) + sum1[i] + c[i]

考虑单调性 K(j) 单调递减x[i]单调递增。维护直线就是一般的单调队列了。

BZOJ 3437 只是把x[i]变成了i,其他的没有变化

而BZOJ 3156 只是在3437的基础上把sum[i]变成i,其他的没有变化。

代码 (1096):

#include 
#include 
#include 
using namespace std;
const int N = 1200000;
#define int long long
#define ll long long
#define K(i) (-s[i])
#define B(i) (f[i]+x[i]*s[i]-s1[i])
#define Y(i, j) (K(j)*x[i]+B(j))
int x[N], p[N], c[N], s[N], s1[N], f[N];
int q[N], l, r;
bool cmp(int i,int j,int k) {
    ll x1=(K(i)-K(k))*(B(j)-B(i));
    ll x2=(K(i)-K(j))*(B(k)-B(i));
    return x1>=x2;
}
signed main() {
    int n;
    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];
        s1[i]=s1[i-1]+s[i-1]*(x[i]-x[i-1]);
    }
    for(int i = 1; i <= n; i ++ ) {
        while(l < r && Y(i, q[l]) >= Y(i, q[l+1])) l++;
        f[i] = Y(i,q[l])+s1[i]+c[i];
        while(l < r&& cmp(i, q[r-1], q[r])) r--;
        q[++r] = i;
    }
    printf("%lld\n", f[n]);
}

发表评论

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