仓库建设

容易想到，我们必须在最低点也就是第n个点建设一个仓库。由此想到这样设状态：f[i]表示仅处理1~i的工厂的最小花费。

找到一个j<i，在j处建工厂，从j+1到i-1的都运到i处，那么推出状转方程：f[i]=min{f[j]+c[i]+p[k]*(x[i]-x[k])},k从i+1到j-1

预处理两个前缀和，设sp为p的前缀和，spx为p*x的前缀和。

可以推出简化版的N^2的状转方程：f[i]=min{f[j]+c[i]+x[i]*(sp[i-1]-sp[j])-spx[i-1]+spx[j]}

写成一次函数的形式：f[j]+spx[j]=x[i]*sp[j]+f[i]-c[i]-x[i]*sp[i-1]+spx[i-1],其中y=f[j]+spx[j],k=x[i],x=sp[j],b=f[i]-c[i]-x[i]*sp[i-1]+spx[i-1]

数据保证了x[i]单调递增，非常好！！！

看代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1000000+10;
int c[maxn],x[maxn],p[maxn],q[maxn];
int sp[maxn],spx[maxn],f[maxn],n;
inline int yval(int a,int b){
    return f[b]-f[a]+spx[b]-spx[a];
}
inline int xval(int a,int b){
    return sp[b]-sp[a];
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld%lld",&x[i],&p[i],&c[i]);
        sp[i]=sp[i-1]+p[i];
        spx[i]=spx[i-1]+p[i]*x[i];
    }
    memset(f,0x3f,sizeof(f));
    f[0]=0;
    int l=1,r=1;
    q[l]=0;
    for(int i=1;i<=n;i++){
        while(l<r&&yval(q[l],q[l+1])<=xval(q[l],q[l+1])*x[i])l++;
        f[i]=f[q[l]]+c[i]+x[i]*(sp[i-1]-sp[q[l]])-spx[i-1]+spx[q[l]];
        while(l<r&&yval(q[r-1],q[r])*xval(q[r],i)>=xval(q[r-1],q[r])*yval(q[r],i))r--;
        q[++r]=i;
    }
    printf("%lld
",f[n]);
    return 0;
}