题面在这里
题意
L公司有(n)个工厂，由高到底分布在一座山上，工厂1在山顶，工厂N在山脚，工厂(i)到工厂1的距离为(x[i])。
第(i)个工厂目前已有成品(p[i])件，在第(i)个工厂位置建立仓库的费用是(c[i])。
对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于L公司产品的对外销售处设置在山脚的工厂(n)，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，假设一件产品运送1个单位距离的费用是1。
请你帮助L公司寻找一个仓库建设的方案，使得总的费用（建造费用+运输费用）最小。
数据范围
(Nle1000000)。 所有的(x[i]),(p[i]),(c[i])均在32位带符号整数以内，保证中间计算结果不超过64位带符号整数。
sol
设(f[i])表示在第(i)个工厂建立仓库，并将前(i)个工厂里的货物处理完毕的最小费用，那么可以建立一个朴素的方程
[f[i]=min_{j=0}^{i-1}[f[j]+c[i]+sum_{k=j+1}^{i}p[k](x[i]-x[k])]
]
[f[i]=min_{j=0}^{i-1}[ f[j]+c[i]+x[i]sum_{k=j+1}^{i}p[k]-sum_{k=j+1}^{i}x[k]p[k] ]
]
这样使用部分和优化后复杂度是(O(n^2))
记(a[i]=sum_{k=1}^{i}p[k])，(b[i]=sum_{k=1}^{i}x[k]p[k])，那么有
[f[i]=min_{j=0}^{i-1}[f[j]+c[i]+x[i](a[i]-a[j])-(b[i]-b[j])]
]
[=min_{j=0}^{i-1}(f[j]+b[j]-x[i]a[j])+c[i]+x[i]a[i]-b[i]
]
记(a[j]=x_j)，(f[j]+b[j]=y_j)，(x[i]=k_i)，那么有
[f[i]-c[i]-x[i]a[i]+b[i]=min_{j=0}^{i-1}(y_j-k_ix_j)
]
斜率优化完成
由于(k_i=x[i])单调递增，所以使用单调队列，时间复杂度为(O(n))
代码
#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<complex>
#include<vector>
#include<cstdio>
#include<string>
#include<bitset>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
#define mp make_pair
#define pb push_back
#define RG register
#define il inline
using namespace std;
typedef unsigned long long ull;
typedef vector<int>VI;
typedef long long ll;
typedef double dd;
const dd eps=1e-10;
const int mod=1e8;
const int N=1000010;
il ll read(){
RG ll data=0,w=1;RG char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
if(ch=='-')w=-1,ch=getchar();
while(ch<='9'&&ch>='0')data=data*10+ch-48,ch=getchar();
return data*w;
}
il void file(){
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
}
ll n,x[N],p[N],c[N],a[N],b[N],f[N];
struct node{ll x,y;}Q[N];ll L=1,R;
il ll query(ll k){
while(L<R&&k*(Q[L+1].x-Q[L].x)>Q[L+1].y-Q[L].y)L++;
return Q[L].y-k*Q[L].x;
}
il void insert(node q){
while(L<R&&(Q[R].y-Q[R-1].y)*(q.x-Q[R].x)>(q.y-Q[R].y)*(Q[R].x-Q[R-1].x))R--;
Q[++R]=q;
}
int main()
{
n=read();
for(RG int i=1;i<=n;i++){
x[i]=read();p[i]=read();c[i]=read();
a[i]=a[i-1]+p[i];b[i]=b[i-1]+x[i]*p[i];
}
insert((node){0,0});
for(RG int i=1;i<=n;i++){
f[i]=query(x[i])+c[i]+x[i]*a[i]-b[i];
insert((node){a[i],f[i]+b[i]});
}
printf("%lld
",f[n]);
return 0;
}