过程：
$f[i]=min(f[j]+\sum_{k=j+1}^{i}p_{k}*(x_{i}-x_{k}))+c[i]$
令$sum[i]=\sum_{j=1}^{i}p_{k},sumx[i]=\sum_{j=1}^{i}p_{k}*x_{k}$
$f[i]=min(f[j]+(sum[i]-sum[j])*x[i]-(sumx[i]-sumx[j]))+c[i]$
若$j$比$k$优
$f[j]+(sum[i]-sum[j])*x[i]-(sumx[i]-sumx[j])<=f[k]+(sum[i]-sum[k])*x[i]-(sumx[i]-sumx[k])$
$f[j]-f[k]<=(sum[j]-sum[k])*x[i]+sumx[k]-sumx[j]$
$\frac{f[j]-f[k]+sumx[j]-sumx[k]}{sum[j]-sum[k]}<=x[i]$
（未过BZOJ）
#include<iostream> #include<cstdio> #include<cstring> #define ll long long using namespace std; const int maxn=1e6+9; int n,x[maxn],p[maxn],c[maxn]; ll s[maxn],sx[maxn],f[maxn]; //s[i]=sumpi sx[i]=sum(pi*xi) //f[j]-f[k]+sx[i]-sx[k]<=x[i]*(s[j]-s[k]) int q[maxn]; inline ll up(int j,int k){ return f[j]-f[k]+sx[j]-sx[k]; } inline ll down(int j,int k){ return s[j]-s[k]; } inline ll dp(int i,int j){ return f[j]+(s[i]-s[j])*x[i]-(sx[i]-sx[j])+c[i]; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d%d%d",&x[i],&p[i],&c[i]),s[i]=s[i-1]+p[i],sx[i]=sx[i-1]+(ll)p[i]*x[i]; int head=1,tail=1; for(int i=1;i<=n;i++){ while(head<tail && up(q[head+1],q[head])<=x[i]*down(q[head+1],q[head]))head++; f[i]=dp(i,q[head]); while(head<tail && up(i,q[tail])*down(q[tail],q[tail-1])<=up(q[tail],q[tail-1])*down(i,q[tail]))tail--; q[++tail]=i; } printf("%d",f[n]); }
原文：https://www.cnblogs.com/superminivan/p/11299576.html