题目描述
https://www.luogu.com.cn/problem/P2120
题解
设,
$S_i$即为前个工厂的物品总数,为前个工厂都把所有物品运到工厂的总花费(虽然不能运到仓库)
设表示把前个工厂的物品都运到仓库里且在工厂处建立仓库的最小花费
则有
变化一下式子就是
使用斜率优化即可
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45
| #include <bits/stdc++.h> #define N 1000005 using namespace std; typedef long long ll;
template <typename T> inline void read(T &num) { T x = 0, f = 1; char ch = getchar(); for (; ch > '9' || ch < '0'; ch = getchar()) if (ch == '-') f = -1; for (; ch <= '9' && ch >= '0'; ch = getchar()) x = (x << 3) + (x << 1) + (ch ^ '0'); num = x * f; }
int n, head, tail, q[N]; ll a[N], p[N], c[N], dp[N], sum[N], sum2[N], K[N];
inline ll getx(int id) { return sum[id]; } inline ll gety(int id) { return dp[id] + sum2[id]; } inline double slope(int x, int y) { return getx(x) == getx(y) ? 1e15 : 1.0 * (gety(x) - gety(y)) / (getx(x) - getx(y)); }
int main() { read(n); for (int i = 1; i <= n; i++) { read(a[i]); read(p[i]); read(c[i]); sum[i] = sum[i-1] + p[i]; sum2[i] = sum2[i-1] + a[i] * p[i]; K[i] = a[i]; } q[head=tail=1] = 0; for (int i = 1; i <= n; i++) { while (head < tail && slope(q[head], q[head+1]) < K[i]) head++; int j = q[head]; dp[i] = dp[j] + a[i] * (sum[i] - sum[j]) - (sum2[i] - sum2[j]) + c[i]; while (head < tail && slope(q[tail-1], q[tail]) > slope(q[tail], i)) tail--; q[++tail] = i; } printf("%lld\n", dp[n]); return 0; }
|