题目大意： 有n个工厂，每个工厂到第一个工厂的距离为li，每个工厂有pi件货物，现在需要在一些工厂上建设仓库存储货物，费用为costi。 工厂i的物品可以在i~n的工厂内存放，运送到工厂j需要（lj-li）*pi的费用。 求存放所有货物的最小花费。
题目分析： 可以容易的想到动态规划。
设ｆ［ｉ］代表在ｉ位置建立工厂，存放１～ｉ的货物的最小花费。 设ｓｕｍ［ｉ］＝∑（１～ｉ）ｐｉ （代表前ｉ个工厂的物品和） 设ｔｒａｎｓ［ｉ］＝∑（１～ｉ）ｓｕｍ［ｉ－１］＊（ｌ［ｉ］－ｌ［ｉ－１］） （代表把所有物品运送至工厂ｉ的花费）
递推公式为： ｆ［ｉ］＝ｍｉｎ｛ｆ［ｊ］＋ｔｒａｎｓ［ｉ］－ｔｒａｎｓ［ｊ］－ｓｕｍ［ｊ］＊（ｌ［ｉ］－ｌ［ｊ］＋ｃｏｓｔ［ｉ］）｝
（枚举前面的每一个位置ｊ，ｊ之前的答案为ｆ［ｊ］，ｆ［ｉ］的答案即为ｆ［ｊ］加上ｊ到ｉ之间所有货物运送到位置ｉ的费用，不过这里不是重点）
这样做时间复杂度是Ｏ（ｎ＾２）的，显然时间爆炸。 考虑优化。
假设ｉ位置的答案可由位置ｊ转移。 ｆ［ｉ］＝ｆ［ｊ］＋ｔｒａｎｓ［ｉ］－ｔｒａｎｓ［ｊ］－ｓｕｍ［ｊ］＊（ｌ［ｉ］－ｌ［ｊ］＋ｃｏｓｔ［ｉ］）
把括号打开，把和ｉ相关的放到一起，把和ｊ相关的放到一起：
ｆ［ｉ］－ｔｒａｎｓ［ｉ］－ｃｏｓｔ［ｉ］＝ｆ［ｊ］＋ｓｕｍ［ｊ］＊ｌ［ｊ］－ｔｒａｎｓ［ｊ］－ｓｕｍ［ｊ］＊ｌ［ｉ］
设Ｐ＝ｆ［ｉ］－ｔｒａｎｓ［ｉ］－ｃｏｓｔ［ｉ］ 设ｙ＝ｆ［ｊ］＋ｓｕｍ［ｊ］＊ｌ［ｊ］－ｔｒａｎｓ［ｊ］ 设ｘ＝ｓｕｍ［ｊ］ 设ｋ＝ｌ［ｉ］ 于是上述式子就转化为： Ｐ＝ｙ－ｋｘ 即ｙ＝ｋｘ＋Ｐ，为一次函数形式。 此时除了要求的ｆ［ｉ］与ｉ有关的值都可以视为定值，所以斜率ｋ为定值。 可以将有关ｊ的答案看做是平面上的一些点，我们现在想要求ｆ［ｉ］的最小值，即求Ｐ的最小值。 我们可以通过严格的证（ｈｕａ）明（ｔｕ）得知，最优解一定在凸包所代表的点上： 并且观察到最优答案点左侧的斜率小于ｋ，右侧斜率大于ｋ，只要直接找到这个点直接更新答案即可。 观察发现：ｘ是递增的，所以凸包可以线性维护。 观察发现：ｋ是递增的，所以答案点在凸包上也是递增的，所以可以线性查找，直接向右找。 这样更新答案是线性时间复杂度。 总时间复杂度为Ｏ（ｎ）。
代码如下：
#include <cstdio> #define N 1200000 using namespace std; typedef long long LL; struct point{ LL x,y; point(LL x=0,LL y=0):x(x),y(y){} LL operator * (const point &c) const { return x*c.y-y*c.x; } point operator - (const point &c) const { return point(x-c.x,y-c.y); } }h[N]; int n; LL l[N],sum[N],trans[N],f[N],cost[N]; int top=0; void convex_hull(point x) { while(top>1 && (h[top]-h[top-1])*(x-h[top-1])<=0) top--; h[++top]=x; return; } bool judge(int now,long long k) { if(now!=top && h[now+1].y-h[now].y<k*(h[now+1].x-h[now].x)) return false; return true; } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%lld%lld%lld",&l[i],&sum[i],&cost[i]); sum[i]+=sum[i-1]; trans[i]=trans[i-1]+sum[i-1]*(l[i]-l[i-1]); } int now=1; convex_hull(point(0,0)); for(int i=1;i<=n;i++) { while(!judge(now,l[i])) now++; f[i]=h[now].y-l[i]*h[now].x+trans[i]+cost[i]; convex_hull(point(sum[i],f[i]+sum[i]*l[i]-trans[i])); now=now>top?top:now; } printf("%lld\n",f[n]); return 0; }