算法1

斜率优化dp $O(n)$

令 sumpx[i]为 p[i]x[i]的前缀和， sump[i]为 p[i]的前缀和
dp：f[i]表示前i个工厂建仓库的最小花费。(显然i位置肯定是要建工厂的)
f[i] = min{f[j]+c[i]+x[i](sump[i-1]-sump[j])-(sumpx[i-1]-sumpx[j])

移项：f[j]+sumpx[j] = x[i]sump[j] + f[i] + sumpx[i-1]- c[i] - x[i]sump[i-1]
对于每一个点（sump[j], f[j]+sumpx[j]） 其斜率与i有关，为x[i]。 题目可以变为斜率优化的问题

其中这个题目中满足两个性质：
1. x[i]显然随着i增加单调增加， 即斜率是单调递增的，所以要不断消除凸包的头
2. sump[j] 显然随着j的增加 x坐标 也是增加的，即新加入的点一定在凸包上。

时间复杂度

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int N=1000010, INF=0x3f3f3f3f;
LL f[N], sumpx[N], sump[N], p[N], c[N], x[N], q[N];
int n;
double long check(int i, int j){
    return (f[i]+sumpx[i]-f[j]-sumpx[j])*1.0/(sump[i]-sump[j]);
}
int main(){
    scanf("%d", &n);
    memset(f, INF, sizeof(f));
    for(int i=1; i<=n; i++){
        scanf("%lld %lld %lld", &x[i], &p[i], &c[i]);
        //cin>>x[i]>>p[i]>>c[i];
        sumpx[i] = sumpx[i-1]+p[i]*x[i];
        sump[i] = sump[i-1]+p[i];
    }
    f[0] = 0;
    int hh=0, tt=0;
    q[0] = 0;
    for(int i=1; i<=n; i++){
        while(hh<tt && check(q[hh+1], q[hh])<x[i]) hh++;
        int j = q[hh]; 
        f[i] = f[j]+c[i]+x[i]*(sump[i-1]-sump[j])-(sumpx[i-1]-sumpx[j]);
        while(hh<tt && check(q[tt], q[tt-1])>=check(i,q[tt-1])) tt--;
        q[++tt] = i;
    }
    cout<<f[n]<<endl;
}