link
其实是一个需要许多次换元的$dp$，比较简单。
我们通过层层操作以后得到式子$f[j]+s[j]=d[i]\times k[j]+s[i]-val[i]-d[i]\times k[i]+f[i]$
然后会发现里面的横坐标$(X)$，纵坐标$(Y)$与斜率，然后发现还是维护下凸壳，然后就单调队列优化即可
#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #define int long long using namespace std; inline int read(){int f=1,ans=0;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){ans=ans*10+c-'0';c=getchar();}return f*ans; } const int N=1000001; int n,f[N],d[N],sum[N],val[N],k[N],s[N],c[N],p[N],X[N],Y[N],que[N],l,r; signed main(){memset(f,127/3,sizeof(f));f[0]=0;n=read();for(int i=1;i<=n;i++) d[i]=read(),sum[i]=sum[i-1]+d[i],c[i]=read(),val[i]=read();for(int i=1;i<=n;i++) k[i]=k[i-1]+c[i];for(int i=1;i<=n;i++) p[i]=d[i]*c[i];for(int i=1;i<=n;i++) s[i]=s[i-1]+p[i];l=1,r=1,que[1]=0,X[0]=k[0],Y[0]=f[0]+s[0];for(int i=1;i<=n;i++){while(l<r&&Y[que[l+1]]-Y[que[l]]<=(X[que[l+1]]-X[que[l]])*d[i])l++;f[i]=f[que[l]]+val[i]+d[i]*(k[i]-k[que[l]])-(s[i]-s[que[l]]);X[i]=k[i],Y[i]=f[i]+s[i];while(l<r&&(Y[que[r]]-Y[que[r-1]])*(X[i]-X[que[r]])>=(Y[i]-Y[que[r]])*(X[que[r]]-X[que[r-1]])) r--;que[++r]=i;}cout<<f[n]; }