题链：
http://www.lydsy.com/JudgeOnline/problem.php?id=1096
题解：
斜率优化DP
$（d_i：i 位置到1位置的距离，p_i：i位置的成品数量，c_i：i位置建仓库的费用）$
先来定义dp数组：
令DP[i]表示在i位置建立仓库，且1～i位置都安排完毕的最小总花费。
转移：
$DP[i]=min(DP[j]+W(j+1{～}i位置的物品挪动到i位置的代价)+c_i)$
看看W如何计算：
$W=(d_i-d_{i})p_{i}+(d_i-d_{i-1})p_{i-1}+\cdots+(d_i-d_{j+1})p_{j+1}$
$\quad=d_i(p_i+p_{i-1}+\cdots+p_{j+1})-(d_{i}p_{i}+d_{i-1}p_{i-1}+\cdots+d_{j+1}p_{j+1})$
令$sump_i=p_i+p_{i-1}+\cdots+p_{1}$，$sumdp_i=d_ip_i+d_{i-1}p_{i-1}+\cdots+d_{1}p_{1}$
所以
$W=d_i(sump_i-sump_j)-(sumdp_i-sumdp_j)$
$\quad=d_isump_i-sumdp_i-d_isump_j+sumdp_j$
然后把W写进DP转移，(若j转移给i的话)：
$DP[i]=(d_isump_i-sumdp_i+c_i)-(d_isump_j)+(sumdp_j+DP[j]))$
一个典型的可以用斜率优化的转移。
令 $Y_j=DP[j]+sumdp_j$
若对于当前计算的DP[i],存在两个转移来源点 k，j，k < j，且j优于k
则得到
$Y_j-d_isump_j-(Y_k-d_isump_k)<0$
化简：$\frac{Y_j-Y_k}{sump_j-sump_k}<d_i$
令Slope(j,k)=$\frac{Y_j-Y_k}{sump_j-sump_k}$，
则得到结论：$若k < j，且Slope(j,k)<d_i，则j优于k$。
那么如果存在 k<j<i,且Slope(i,j)<Slope(j,k)，则j是无效点，舍去。
同时注意到$d_i$单增，所以可以用单调队列维护。
最终的复杂度 O(N)
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 1000050
#define ll long long
using namespace std;
ll d[MAXN],p[MAXN],c[MAXN];
ll DP[MAXN],sump[MAXN],sumdp[MAXN];
int N;
struct Moque{
int q[MAXN],l,r;
#define Y(j) (DP[j]+sumdp[j])
#define X(j) (sump[j])
#define Slope(j,k) (1.0*Y(j)-Y(k))/(1.0*X(j)-X(k))
void Reset(){l=r=1;q[1]=0;}
void Push(int i){
if(l<=r&&X(i)==X(q[r]))
{if(Y(i)<Y(q[r])) r--; else return;}
while(l+1<=r&&Slope(i,q[r])<Slope(q[r],q[r-1])) r--;
q[++r]=i;
}
int Query(int i){
while(l+1<=r&&Slope(q[l+1],q[l])<d[i]) l++;
return q[l];
}
}Q;
void read(ll &x){
static int sn; static char ch;
x=0; sn=1; ch=getchar();
while(ch<'0'||'9'<ch){if(ch=='-')sn=-1;ch=getchar();}
while('0'<=ch&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
x=x*sn;
}
int main(){
scanf("%d",&N);
for(int i=1;i<=N;i++){
read(d[i]); read(p[i]); read(c[i]);
sump[i]=p[i]+sump[i-1];
sumdp[i]=d[i]*p[i]+sumdp[i-1];
}
Q.Reset();
for(int i=1,j;i<=N;i++){
j=Q.Query(i);
DP[i]=d[i]*sump[i]-sumdp[i]+c[i]-d[i]*sump[j]+sumdp[j]+DP[j];
Q.Push(i);
}
printf("%lld",DP[N]);
return 0;
}