描述 Description
L 公司有 N 个工厂，由高到底分布在一座山上。如图所示，工厂 1 在山顶，工厂 N 在山脚。 由于这座山处于高原内陆地区（干燥少雨），L 公司一般把产品直接堆放在露天，以节省费用。突然有一天，L 公司的总裁 L 先生接到气象部门的电话，被告知三天之后将有一场暴雨，于是 L 先生决定紧急在某些工厂建立一些仓库以免产品被淋坏。由于地形的不同，在不同工厂建立仓库的费用可能是不同的。第 i 个工厂目前已有成品 Pi 件，在第 i 个工厂位置建立仓库的费用是 Ci。对于没有建立仓库的工厂，其产品应被运往其他的仓库进行储藏，而由于 L 公司产品的对外销售处设置在山脚的工厂 N，故产品只能往山下运（即只能运往编号更大的工厂的仓库），当然运送产品也是需要费用的，假设一件产品运送 1 个单位距离的费用是 1。假设建立的仓库容量都都是足够大的，可以容下所有的产品。你将得到以下数据： 工厂 i 距离工厂 1 的距离 Xi（其中 X1=0）; 工厂 i 目前已有成品数量 Pi; 在工厂 i 建立仓库的费用 Ci; 请你帮助 L 公司寻找一个仓库建设的方案，使得总的费用（建造费用 + 运输费用）最小。
输入格式 InputFormat
第一行包含一个整数 N，表示工厂的个数。接下来 N 行每行包含两个整数 Xi, Pi, Ci, 意义如题中所述。
输出格式 OutputFormat
仅包含一个整数，为可以找到最优方案的费用。
样例输入 SampleInput
3
0 5 10
5 3 100
9 6 10
样例输出 SampleOutput
32
斜率优化 DP。和 小 P 的牧场 那题一样的。。。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
const ll maxn=1000005;
ll i,j,t,n,m,l,r,k,z,y,x;
ll a[maxn],sum1[maxn],sum2[maxn],c[maxn],p[maxn];
ll f[maxn],q[maxn];
ll head,tail;
inline ll fracup(ll x,ll y)
{
return f[x]-f[y]+sum2[x]-sum2[y];
}
inline ll fracdown(ll x,ll y)
{
return sum1[x]-sum1[y];
}
int main()
{
scanf("%lld",&n);
sum1[0]=sum2[0]=0;
for (i=1;i<=n;i++) scanf("%lld%lld%lld",&a[i],&p[i],&c[i]),sum1[i]=sum1[i-1]+p[i],sum2[i]=sum2[i-1]+a[i]*p[i];
head=tail=0;q[tail]=0;
for (i=1;i<=n;i++)
{
while (tail>head && fracup(q[head+1],q[head])<a[i]*fracdown(q[head+1],q[head])) head++;
t=q[head];
f[i]=f[t]+a[i]*(sum1[i]-sum1[t])-sum2[i]+sum2[t]+c[i];
while (tail>head && fracup(q[tail],q[tail-1])*fracdown(i,q[tail])>fracup(i,q[tail])*fracdown(q[tail],q[tail-1])) tail--;
q[++tail]=i;
}
printf("%lld\n",f[n]);
return 0;
}