题解 P2120 【[ZJOI2007]仓库建设】

· · 题解

Solution

斜率优化dp。设 dp_i 为在 i 位置建设了仓库的最小代价。

则有

dp_i=\min\limits_{0 \leq j<i} \{dp_j+x_i\times\sum\limits_{l=j+1}^{i}(p_l) -\sum\limits_{l=j+1}^{i}(x_l \times p_l)\}+c_i

用前缀和优化，令 sump_i=\sum\limits_{j=1}^{i}p_i,sum_i=\sum\limits_{j=1}^{i}x_i\times p_i，则原式转为

dp_i=\min\limits_{0 \leq j < i}\{dp_j+x_i\times(sump_i-sump_j)-(sum_i-sum_j)\}+c_i

若决策 j 优于决策 k ，则

dp_j+x_i\times(sump_i-sump_j)-(sum_i-sum_j)<dp_k+x_i\times(sump_i-sump_k)-(sum_i-sum_k)

化简得

(dp_j+sum_j)-(dp_k+sum_k)<x_i \times (sump_j-sump_k)

即

\frac{(dp_j+sum_j)-(dp_k+sum_k)}{sump_j-sump_k}<x_i

令 Y(x)=dp_x+sum_x,X(x)=sump_x，则

\frac{Y(j)-Y(k)}{X(j)-X(k)}<x_i

上斜率优化即可

Code

#include <iostream>
#include <cstdlib>
#include <cstdio>
#define int long long
#define rep(i, l, r) for(register int i = l; i <= r; i++)
#define per(i, r, l) for(register int i = r; i >= l; i--)

using namespace std;
const int N = 10010000;
int n, x[N], p[N], c[N], dp[N];
int sum[N], sump[N], h, t, Q[N];
inline int Y(int i) {
    return dp[i] + sum[i];
}
inline int X(int i) {
    return sump[i];
}
inline double slope(int j, int k) {
    return 1.0 * (Y(j) - Y(k)) / (X(j) - X(k));
}
signed main() {
    scanf("%d", &n);
    rep(i, 1, n) {
        scanf("%d%d%d", &x[i], &p[i], &c[i]);
        sump[i] = sump[i - 1] + p[i];
        sum[i] = sum[i - 1] + x[i] * p[i];
    }
    rep(i, 1, n) {
        while(h < t && slope(Q[h + 1], Q[h]) < x[i]) h++;
        int j = Q[h]; dp[i] = dp[j] + x[i] * (sump[i] - sump[j]) - sum[i] + sum[j] + c[i];
        while(h < t && slope(Q[t], Q[t - 1]) > slope(i, Q[t])) t--; Q[++t] = i;
    }
    printf("%lld\n", dp[n]);
    return 0;
}