Description
L公司有N个工厂，由高到底分布在一座山上。如图所示，工厂1在山顶，工厂N在山脚。由于这座山处于高原内陆地区（干燥少雨），L公司一般把产品直接堆放在露天，以节省费用。突然有一天，L公司的总裁L先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是L先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第i个工厂目前已有成品Pi件，在第i个工厂位置建立仓库的费用是Ci。对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于L公司产品的对外销售处设置在山脚的工厂N，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，假设一件产品运送1个单位距离的费用是1。假设建立的仓库容量都都是足够大的，可以容下所有的产品。你将得到以下数据：1：工厂i距离工厂1的距离Xi（其中X1=0）;2：工厂i目前已有成品数量Pi;:3：在工厂i建立仓库的费用Ci;请你帮助L公司寻找一个仓库建设的方案，使得总的费用（建造费用+运输费用）最小。n<=10^6
第一感觉网络流，看完：斜率优化？？？
n^2的dp式：dp[i]=min(dp[j]+∑k=j+1i(xi-xk)*pk)+c[i]
转化一下：dp[i]=min(dp[j]+xi*∑k=j+1ipk - ∑k=j+1ixk*pk)+ci
发现对于每个i，前面的dp式可以抽象成直线，并且，随着j的增大，k减小，x递增。可以斜率优化。然后。。。
woc？？这个k和b是变的？？？后来仔细想了一下，每个队列中维护的k和b当轮到一个新的i的时候增加的量和减少的量是相同的，所以说相当于：b变大->图像上移，k变大->图像逆时针方向扭曲。
所以说斜率优化本质不变，也就是每条直线的交点在横坐标上的投影相对位置不变，k和b的相对大小也不变。所以，然并卵。
其他的想说的是：h<t，队首拿，队尾加，h,t起始都为0；
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1001000
using namespace std;
typedef long long ll;
int n,dis[N],p[N],c[N];
ll sp[N],sxp[N],dp[N];
int q[N],h,t;
ll k(int x,int y) {return sp[y]-sp[x];}
ll b(int x,int y) {return dp[x]-(sxp[y]-sxp[x]);}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&dis[i],&p[i],&c[i]);
for(int i=1;i<=n;i++)
sp[i]=sp[i-1]+p[i],sxp[i]=sxp[i-1]+1ll*dis[i]*p[i];
for(int i=1;i<=n;i++)
{
while(h<t&&k(q[h],i)*dis[i]+b(q[h],i)>=k(q[h+1],i)*dis[i]+b(q[h+1],i)) h++;
dp[i]=k(q[h],i)*dis[i]+b(q[h],i)+c[i];
while(h<t&&i!=n&&(b(q[t],i+1)-b(i,i+1))*(k(q[t],i+1)-k(q[t-1],i+1))<=(b(q[t-1],i+1)-b(q[t],i+1))*(k(i,i+1)-k(q[t],i+1))) t--;
q[++t]=i;
}
printf("%lld",dp[n]);
return 0;
}