自动搬运

查看原文

来自洛谷，原作者为

	Aisaka_Taiga 在莴苣叶下避雨的喵喵会不会在失去莴苣后振作起来呢||AFO

搬运于2025-08-24 21:34:14，当前版本为作者最后更新于2023-11-14 20:20:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

咱可以设 $f_{i}$ 表示第 $i$ 个工厂建工厂，只考虑前 $i$ 个工厂不被冲的最小花费。

那么咱就能写出来一个 $O(n^2)$ 的 DP 式子：

$$f_{i} = \min_{j=1}^{i -1}(f_j + \sum_{k = j + 1}^{i} (x_i - x_k) \times p_k + c_i) $$

复杂度肯定受不了，我们先拆一下式子：

$$f_i=\min_{j=1}^{i-1}(f_{j}+\sum_{k = j + 1}^{i}x_i\times p_k - \sum_{k = j + 1}^{i}x_{k}\times p_k + c_i) $$

咱设 $s_i = \sum_{k=1}^{i}p_k\times x_k$，然后对 $p$ 数组做一次前缀和。

那么咱就可以简化成这样：

$$f_i = \min_{j=1}^{i-1}(f_j + x_i \times (p_i - p_j) - s_i + s_j + c_i) $$

假设前面有两个位置 $a, b$，且 $a<b$ 那么如果 $a$ 转移过来优于 $b$，需要满足：

$$f_a+x_i\times(p_i-p_a) - s_i +s_a + c_i > f_b+x_i\times(p_i-p_b) - s_i +s_b + c_i $$$$f_a-f_b+x_i\times(p_i-p_a-p_i+p_b)<-s_i+s_b+c_i+s_i-s_a-c_i $$$$f_a-f_b+x_i\times(p_b-p_a)< s_b - s_a$$ $$x_i\times(p_b-p_a) < s_b-s_a-f_a+f_b$$ $$x_{i}<\frac{s_b-s_a-f_a+f_b}{p_b-p_a}$$ $$x_{i}<\frac{(f_b+s_b)-(f_a+s_a)}{p_b-p_a}$$

右边的这个东西可以看作是由 $(p_i,f_i+s_i)$ 这类点的两个点构成的直线的斜率，既然 $p_i, x_i$ 单调递增，也就是说斜率需要越来越大，咱就可以维护一个下凸壳。

开一个队列，设 $q_t$ 为队尾元素，那么根据上面的式子，若通过 $q_t,i$ 两个点的直线斜率小于等于通过 $q_{t-1},q_t$ 两点的直线，那么就应该弹出 $q_t$。

最后有的工厂可能没有商品，所以此时会出现相邻两个点构成的直线中 $p_i-p_j=0$，此时咱想到横坐标相同的两个点，显然应该是要纵坐标更小的。

所以若 $y>0$ 就当作是正无穷，反之则为负无穷，若 $y=0$ 则无所谓。

/*
 * @Author: Aisaka_Taiga
 * @Date: 2023-11-14 16:17:16
 * @LastEditTime: 2023-11-14 19:42:44
 * @LastEditors: Aisaka_Taiga
 * @FilePath: \Desktop\P2120.cpp
 * The heart is higher than the sky, and life is thinner than paper.
 */
#include <bits/stdc++.h>

#define int long long
#define DB double
#define N 1000010

using namespace std;

inline int read()
{
    int x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -1; c = getchar();}
    while(c <= '9' && c >= '0') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x * f;
}

int n, c[N], p[N], x[N], s[N], q[N], f[N], ans = 1e18;

/*
f[i] = min(f[j] + \sum_{k = j + 1}^{i} (x[i] - x[k]) * p[k] + c[i]);
f[i] = min(f[j] + \sum_{k = j + 1}^{i} (x[i] * p[k]) - \sum_{k = j + 1}^{i} x[k] * p[k] + c[i]);
s[i] = \sum_{k = 1}^{i} p[k] * x[k], p[i] = \sum_{k = 1}^{i} p[k];
f[i] = min(f[j] + x[i] * (p[i] - p[j]) - s[i] + s[j] + c[i]);
f[i] = min(f[j] + x[i] * p[i] - x[i] * p[j] - s[i] + s[j] + c[i]);
f[j] = x[i] * p[j] + f[i] - x[i] * p[i] + s[i] - s[j] - c[i];???
*/

inline DB xl(int i, int j)
{
    DB y = f[j] - f[i] + s[j] - s[i];
    if(p[j] == p[i])
    {
        if(y == 0) return 0;
        else
        {
            if(y > 0) return 1e19;
            else return -1e19;
        }
    }
    else return y / (p[j] - p[i]);
    return (f[j] - f[i]) * 1.0 / (p[j] - p[i]);
    // return(p[j] == p[i] ? (!y ? 0 : (y > 0 ? 1e19 : -1e19)) : y / DB(p[j] - p[i]));
}

signed main()
{
    n = read();
    for(int i = 1; i <= n; i ++)
    {
        x[i] = read(), p[i] = read(), c[i] = read();
        s[i] = s[i - 1] + p[i] * x[i];
        p[i] += p[i - 1];
    }
    int h = 1, t = 1;
    for(int i = 1; i <= n; i ++)
    {
        while(h < t && xl(q[h], q[h + 1]) <= x[i]) h ++;
        f[i] = f[q[h]] + x[i] * (p[i] - p[q[h]]) - s[i] + s[q[h]] + c[i];
        // cout << "CAO : " << q[h] << endl;
        while(h < t && xl(q[t - 1], i) <= xl(q[t - 1], q[t])) t --;
        q[++ t] = i;
    }
    h = n; ans = f[n];
    while(h && p[h] - p[h - 1] == 0) h --, ans = min(ans, f[h]);
    cout << ans << endl;
    return 0;
}