傳送門
斜率優化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]) f [ i ] = m i n ( f [ j ] + d i s [ i ] ∗ ( s u m p [ i − 1 ] − s u m p [ j ] ) − ( s u m [ i ] − s u m [ j ] ) + c [ i ] )
于是選兩個決策k1,k2并假設k1比k2優。
令 t[k]=f[k]+sum[k] t [ k ] = f [ k ] + s u m [ k ]
=> (t[k1]−t[k2])/(sump[k1]−sump[k2])>dis[i] ( t [ k 1 ] − t [ k 2 ] ) / ( s u m p [ k 1 ] − s u m p [ k 2 ] ) > d i s [ i ]
于是維護一個下凸殼就行了。
代碼：
#include<bits/stdc++.h>
#define ll long long
#define N 1000005
using namespace std;
inline ll read(){
ll ans=,w=;
char ch=getchar();
while(!isdigit(ch)){if(ch=='-')w=-;ch=getchar();}
while(isdigit(ch))ans=(ans<<)+(ans<<)+(ch^),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 *(f[i]+sum[i]-f[j]-sum[j])/(sump[i]-sump[j]);}
int main(){
n=read(),hd=tl=,q[1]=;
for(int i=;i<=n;++i)dis[i]=read(),sump[i]=sump[i-]+read(),sum[i]=sum[i-]+dis[i]*(sump[i]-sump[i-]),c[i]=read();
for(int i=;i<=n;++i){
while(hd<tl&&slope(q[hd+1],q[hd])<*dis[i])++hd;
int j=q[hd];
f[i]=f[j]+dis[i]*(sump[i-]-sump[j])-(sum[i-]-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 ;
}