斜率优化+1，好吧不水分了。

玩具装箱那题以后再做，当作复习吧。

\(f[i]=f[j]-(sum[i]-sum[j])*dis[i]+p[i]\)

\(f[j]=-dis[i]*sum[j]+sum[i]*dis[i]+f[i]-p[i]\)

#include 
    
     #include 
     
      using namespace std;#define ll long longconst int MAXN = 1000010;inline int read(){    int s = 0, w = 1;    char ch = getchar();    while(ch < '0' || ch > '9'){ if(ch == '-') w = -1; ch = getchar(); }    while(ch >= '0' && ch <= '9'){ s = s * 10 + ch - '0'; ch = getchar(); }    return s * w;}int p[MAXN], sum[MAXN], dis[MAXN], q[MAXN], c[MAXN];int n, head, tail;ll ans = 2147483647;ll f[MAXN];inline double k(int i, int j){    return (double)(f[i] - f[j]) / (sum[i] - sum[j]);}int main(){    n = read();    for(int i = 1; i <= n; ++i){       dis[i] = read();       sum[i] = sum[i - 1] + (c[i] = read());       p[i] = read();    }    f[0] = p[n];    for(int i = 1; i <= n; ++i){       dis[i] = dis[n] - dis[i];       f[0] += (ll)dis[i] * c[i];    }    ans = f[0];    for(int i = 1; i < n; ++i){       while(head < tail && k(q[head], q[head + 1]) < -dis[i]) ++head;       int j = q[head];       f[i] = f[j] - (ll)(sum[i] - sum[j]) * dis[i] + p[i];       ans = min(ans, f[i]);       while(head < tail && k(q[tail - 1], q[tail]) >= k(q[tail], i)) --tail;       q[++tail] = i;    }    printf("%lld\n", ans);    return 0;}