https://loj.ac/problem/10189
题目描述
有(N)个工厂建在山上，每个工厂之间有一定的距离，每个工厂有一定的成品和在这个工厂建仓库的代价。成品只能往山脚运，当前(N)有一个仓库，求再建若干个仓库后所有成品运至仓库的最小代价。
思路
由于产品只能从山上往山下运，所以运的必定会是连续的一段，我们记(f[i])为前(i)个工厂的最小代价，记(sum)为(p)的前缀和，(s)为(p*x[i])的前缀和，那么方程为
[f[i]=min{f[j]+sum_{k=j+1}^i p[k]*(x[i]-x[k])}\
f[i]=min{f[j]+x[i]*(sum[i]-sum[j])-s[i]+s[j]}
]
化简为一次函数的形式后为
[f[j]+[j]=x[i]*sum[j]-x[i]*sum[i]+s[i]+f[i]
]
斜率优化维护一下下凸壳求最小截距即可。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+10;
ll read()
{
ll res=0,w=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+(ch^48);ch=getchar();}
return res*w;
}
ll sum[N],s[N],q[N],f[N],x[N],c[N];
int main()
{
ll n=read();
for(ll i=1;i<=n;i++)
{
ll p;
x[i]=read(),p=read(),c[i]=read();
sum[i]=sum[i-1]+p;
s[i]=s[i-1]+(p*x[i]);
}
ll head=0,tail=0;
for(ll i=1;i<=n;i++)
{
while(head<tail&&(f[q[head+1]]+s[q[head+1]]-f[q[head]]-s[q[head]])
<=x[i]*(sum[q[head+1]]-sum[q[head]]))head++;
f[i]=f[q[head]]+x[i]*(sum[i-1]-sum[q[head]])-s[i-1]+s[q[head]]+c[i];
while(head<tail&&(f[q[tail]]+s[q[tail]]-f[q[tail-1]]-s[q[tail-1]])*(sum[i]-sum[q[tail]])
>=(f[i]+s[i]-f[q[tail]]-s[q[tail]])*(sum[q[tail]]-sum[q[tail-1]]))tail--;
q[++tail]=i;
}
printf("%lld",f[n]);
}