$\Large f(i)=min(f(j)+\sum\limits_{k=j+1}^{i}(x_i-x_k)*p_k)+c_i$
显然这样的方程复杂度为$O(n^3)$极限爆炸，所以我们要换一个方程
设$S(i)=\sum\limits_{k=1}^i(x_n-x_k)*p_k$且$A(i)=\sum\limits_{k=1}^ip_k$
则$S(i)-S(j)=\sum\limits_{k=j+1}^i(x_n-x_k)*p_k$,这和原方程很像
最终方程就可以化成
$\Large f(i)=min(f(j)+S(i)-S(j)-(A(i)-A(j))*(x_n-x_i))+c_i$
若对于某个$i$,$j$比$k$优，则
$f(j)+S(i)-S(j)-(A(i)-A(j))*(x_n-x_i)\le f(k)+S(i)-S(k)-(A(i)-A(k))*(x_n-x_i)$
化简得
$\frac{f(j)-S(j)-f(k)+S(k)}{A(j)-A(k)}\le x_i-x_n$
维护一个下凸壳即可
#include<cstdio> #define LL long long #define maxn 1000005 #define inf 0x3fffffffffffffff int x[maxn],p[maxn],c[maxn],que[maxn],s,t=1; LL S[maxn],A[maxn],f[maxn]; LL calc(int i,int j){ if(A[i]==A[j])return inf; return (f[i]-S[i]-f[j]+S[j])/(A[i]-A[j]); } void insert(int i){ while(s<t-1&&calc(i,que[t-1])<=calc(que[t-1],que[t-2]))t--; que[t++]=i; } int main(){ int n;scanf("%d",&n); for(int i=1;i<=n;i++)scanf("%d%d%d",x+i,p+i,c+i),A[i]=A[i-1]+p[i]; for(int i=1;i<=n;i++){ S[i]=S[i-1]+1ll*(x[n]-x[i])*p[i]; while(s<t-1&&calc(que[s+1],que[s])<=x[i]-x[n])s++; int w=que[s]; f[i]=f[w]+S[i]-S[w]-(A[i]-A[w])*(x[n]-x[i])+c[i]; insert(i); } printf("%lld",f[n]); return 0; }
原文：https://www.cnblogs.com/bennettz/p/9086574.html