题解 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 ```cpp #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; } ```