P2120 题解

· · 题解

咱可以设 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;
}