推dp方程

首先将所有的工厂按距离排序

定义f[i]表示前i个工厂的所有货都能够保存下来的最小费用，cost[i][j]为把所有i到j的货物运到j的费用，那么显然

$f[i]=min{ f[j]+cost[j+1][i]+c[i]} (0\leq j \leq i-1)$

考虑如何计算cost[i][j]，定义sum[i]表示前i个工厂的物品个数之和,d[i]表示工厂i到第一个工厂的距离 那么可以得到

$cost[i][j]=cost[1][j]-cost[1][i]-sum[j]*(d[j]-d[i])$

于是只要预处理出cost[1][i]和sum[i]就可以O(1)计算cost[i][j]。下面用cost[i]表示cost[1][i]

看到n这么大，我们试一试斜率优化

假设j>k,且决策j比k优

那么有

$f[j]+cost[i]-cost[j]-sum[j]*(d[i]-d[j])+c[i] < f[k]+cost[i]-cost[k]-sum[k]*(d[i]-d[k])+c[i]$

将所有有关i的移项到右边其他移到左边可以得到

$(f[j]-cost[j])-(f[k]-cost[k])+sum[j]*d[j]-sum[k]*d[k] < d[i]*(sum[j]-sum[k])$

由于sum[j]>sum[k]，可以除过来，否则要考虑不等号变向问题 则

$\frac{(f[j]-cost[j])-(f[k]-cost[k])+sum[j]*d[j]-sum[k]*d[k]}{(sum[j]-sum[k])} < d[i]$ d[i]递增可以斜率优化

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N=1000010;
struct Fact{LL c,d,p;}fa[N];
LL n,cost[N],f[N],sum[N],q[N*3],l,r;
bool cmp(Fact a,Fact b){return a.d<b.d;}
double slop(int k,int j){return (f[j]-cost[j]-(f[k]-cost[k])+sum[j]*fa[j].d-sum[k]*fa[k].d)/(double)(sum[j]-sum[k]);}
void read(LL &x){
	char c;
	while((c=getchar())<'0' || c>'9');x=c-'0';
	while((c=getchar())>='0' && c<='9') x=x*10+c-'0';
}
int main(){
	//freopen("1096.in","r",stdin);freopen("1096.out","w",stdout);
	read(n);
	for(int i=1;i<=n;i++) read(fa[i].d),read(fa[i].p),read(fa[i].c);
	sort(fa+1,fa+n+1,cmp);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+fa[i].p,cost[i]=cost[i-1]+sum[i-1]*(fa[i].d-fa[i-1].d);
	for(int i=1;i<=n;i++){
		while(l<r && slop(q[l],q[l+1])<fa[i].d) l++;
		int j=q[l];
		f[i]=f[j]+cost[i]-cost[j]-sum[j]*(fa[i].d-fa[j].d)+fa[i].c;
		while(l<r && slop(q[r-1],q[r])>slop(q[r],i)) r--;
		q[++r]=i;
	}
	printf("%lld",f[n]);
	return 0;
}