传送门
斜率优化dp经典题。
令f[i]表示i这个地方修建仓库的最优值，那么答案就是f[n]。
用dis[i]表示i到1的距离，sump[i]表示1~i所有工厂的p之和，sum[i]表示1~i所有工厂的p*dis之和。
那么有状态转移方程：
f[i]=min(f[j]+dis[i]∗(sump[i−1]−sump[j])−(sum[i]−sum[j])+c[i])" role="presentation" style="position: relative;">f[i]=min(f[j]+dis[i]∗(sump[i−1]−sump[j])−(sum[i]−sum[j])+c[i])f[i]=min(f[j]+dis[i]∗(sump[i−1]−sump[j])−(sum[i]−sum[j])+c[i])
于是选两个决策k1,k2并假设k1比k2优。
令t[k]=f[k]+sum[k]" role="presentation" style="position: relative;">t[k]=f[k]+sum[k]t[k]=f[k]+sum[k]
=>(t[k1]−t[k2])/(sump[k1]−sump[k2])>dis[i]" role="presentation" style="position: relative;">(t[k1]−t[k2])/(sump[k1]−sump[k2])>dis[i](t[k1]−t[k2])/(sump[k1]−sump[k2])>dis[i]
于是维护一个下凸壳就行了。
代码：
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
inline ll read(){
ll ans=0,w=1;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans*w;
}
int n,q[N],hd,tl;
ll sum[N],sump[N],f[N],dis[N],c[N];
inline double slope(int i,int j){return 1.0*(f[i]+sum[i]-f[j]-sum[j])/(sump[i]-sump[j]);}
int main(){
n=read(),hd=tl=1,q[1]=0;
for(int i=1;i<=n;++i)dis[i]=read(),sump[i]=sump[i-1]+read(),sum[i]=sum[i-1]+dis[i]*(sump[i]-sump[i-1]),c[i]=read();
for(int i=1;i<=n;++i){
while(hd<tl&&slope(q[hd+1],q[hd])<1.0*dis[i])++hd;
int j=q[hd];
f[i]=f[j]+dis[i]*(sump[i-1]-sump[j])-(sum[i-1]-sum[j])+c[i];
while(hd<tl&&slope(q[tl],q[tl-1])>slope(i,q[tl]))--tl;
q[++tl]=i;
}
cout<<f[n];
return 0;
}