测试地址：Print Article
题目大意：要打印一份有N（N≤500000）个词的文章，每个词有一个花费Ci，连续打一段词的花费为(ΣCi)^2+M，M为常数，求打印这份文章的最小花费。
做法：这道题要用到DP的斜率优化。
首先分析题目发现这道题显然可以用动态规划解决，设f[i]为打印前i个词的最小花费，sum[i]为前i个词的花费之和，则状态转移方程为：f[i]=min{f[j]+(sum[i]-sum[j])^2}(0≤j<i)+M，这是一个O(N^2)的式子，然而N可达500000，华丽爆炸，所以需要想办法优化。
我们把min里面的式子展开为f[j]+sum[i]^2-2*sum[i]*sum[j]+sum[j]^2，其中sum[i]^2与j无关，把它从函数里提出来，那么设剩下的式子为G，再令k=2*sum[i]，x=sum[j]，y=f[j]+sum[j]^2，则得G=-kx+y，所以y=kx+G，这个式子很像直线方程的斜截式，那么当G从小变大时，就相当于一条斜率为k的直线从下到上运动，每当接触到一个点(x,y)时都会产生一个合法的G，那么我们要求G的最小值，就要想办法求出这条直线运动时碰到的第一个点。
我们令x[i]=sum[i]，y[i]=f[i]*sum[i]^2，(x[i],y[i])就代表着i这个状态点的坐标，可以看到k和x[i]都是单调不降的，那么我们就对于前面的所有状态点维护一个下凸壳（类似Graham-Scan做凸包），每次求直线与凸壳的切点即可。由于k单调不降，那么我们可以直观的感受到，如果一个点不是i的最优决策点，那么也不会是后面的最优决策点，就可以把i丢掉，对于这个去头去尾和在尾部添加的操作，可以用单调队列实现。由于一个点最多入队一次，出队一次，所以复杂度降为O(N)，问题解决。
注意：比较直线斜率时最好不要直接求斜率来比较，用叉积比较保险，然而也不要搞混不等号的方向。另外删除无用决策点和上凸点的时候，判断叉积正负性是需要加等号的，我也不知道为什么不加就WA......
以下是本人代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,h,t,q[500010];
long long m,sum[500010],f[500010];
struct point
{
long long x,y;
point operator - (point a) const
{
point s;
s.x=x-a.x;
s.y=y-a.y;
return s;
}
}p[500010];
long long multi(point a,point b)
{
return a.x*b.y-b.x*a.y;
}
void solve()
{
h=1,t=1;
q[1]=0;p[0].x=p[0].y=0;f[0]=0;
for(int i=1;i<=n;i++)
{
point now;
now.x=1,now.y=2*sum[i];
while(h<t&&multi(now,p[q[h+1]]-p[q[h]])<=0) h++;
int j=q[h];
f[i]=f[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m;
p[i].x=sum[i],p[i].y=f[i]+sum[i]*sum[i];
while(h<t&&multi(p[i]-p[q[t-1]],p[q[t]]-p[q[t-1]])>=0) t--;
q[++t]=i;
}
}
int main()
{
while(scanf("%d%lld",&n,&m)!=EOF)
{
sum[0]=0;
for(int i=1;i<=n;i++)
{
long long a;
scanf("%lld",&a);
sum[i]=sum[i-1]+a;
}
solve();
printf("%lld
",f[n]);
}
return 0;
}