题意
有 个工厂,每个工厂与第 个工厂的距离为 ,有成品 件。需要修建一些仓库,在每个工厂修建的成本为 。
修建完成后要将成品全部运到仓库里,且只能往序号较大的工厂里运输。运输的成本为 。求成本的最小值。
。
题解
用 表示最后在 修仓库的最小成本,枚举上一次修仓库的位置 ,需要将 的成品都送到 。方程式为:
令 :
有 和 的乘积,考虑斜率优化:
斜率 显然单调。
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
char ch=getchar();
ll f=1,x=0;
while (ch<'0' || ch>'9')
{
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0' && ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return f*x;
}
const int N=1000005;
ll n,x[N],p[N],c[N],s[N],q[N],f[N];
signed main()
{
n=read();
for (ll i=1;i<=n;i++)
{
x[i]=read();
p[i]=read();
s[i]=s[i-1]+x[i]*p[i];
p[i]+=p[i-1];
c[i]=read();
}
ll l=1,r=1; q[l]=0;
for (ll i=1;i<=n;i++)
{
while (l<r && f[q[l+1]]+s[q[l+1]]-f[q[l]]-s[q[l]]
<=(p[q[l+1]]-p[q[l]])*x[i]) l++;
f[i]=f[q[l]]+x[i]*(p[i-1]-p[q[l]])-s[i-1]+s[q[l]]+c[i];
while (l<r && (f[q[r]]+s[q[r]]-f[q[r-1]]-s[q[r-1]])*(p[i]-p[q[r]])
>=(f[i]+s[i]-f[q[r]]-s[q[r]])*(p[q[r]]-p[q[r-1]])) r--;
q[++r]=i;
}
return !printf("%lld",f[n]);
}