题链：
斜率优化DP
一个入门题，就不给题解了，网上的好讲解很多的。
这里就只提一个小问题吧（好吧，个人觉得这个问题也不小）。
本题的输入数据 A[i] 可能会有很讨厌的 0 出现，
这样的话,完全可能导致 k<j，SUM[k]==SUM[j]，DP[k]==DP[j]的情况出现，
所以用double型计算斜率肯定会错啦，因为分母会被减成 0，鬼知道会算出来一个什么。
另外这样写也会出错：
在计算完当前的DP值然后入队时，如果采用这种写法，就会WA。
（新点与队列里倒数第一个点的斜率 < 队列里倒数第一个点和倒数第二个点的斜率 时才弹出队尾。）
正确的应该写成小于等于就弹出
（新点与队列里倒数第一个点的斜率 <= 队列里倒数第一个点和倒数第二个点的斜率 时弹出队尾。）
让我们来看看为什么会这样？
同样是会出现 k<j，SUM[k]==SUM[j]，DP[k]==DP[j]的情况,
那么由本题的解法，计算斜率时，令 X[j]=2*SUM[j]，Y[j]=DP[j]-SUM[j]*SUM[j]
那么反映到平面上，k(X[k],Y[k])，j(X[j],Y[j])就是两个重合的点
这时，如果这两个点都在队列里，（假设j在队尾，k在队列倒数第二个），且又来了一个如下图的新点i要加进队列，会怎样呢？
按算法的逻辑，计算得到i与j的斜率并没有小于j与k的斜率，（再看看判断语句，两边都乘了0），
所以接下来就退出了“弹出队尾”的while循环，然后，我们的下凸包也就没有被维护好：
所以自然错了。
综上，对于本题，因为有0的出现，只有采取 <= 的写法(且不用double计算)才能顺利完成这个入门题。（汗...）
（有点类似求凸包，也要避免重复点带来的影响。）
代码：
#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXN 500050
using namespace std;
int DP[MAXN],SUM[MAXN];
int N,M;
int dx(int a,int b){
return 2*(SUM[a]-SUM[b]);
}
int dy(int a,int b){
return (DP[a]+SUM[a]*SUM[a])-(DP[b]+SUM[b]*SUM[b]);
}
int main(){
static int q[MAXN],l,r;
while(~scanf("%d%d",&N,&M)){
for(int i=1;i<=N;i++)
scanf("%d",&SUM[i]),SUM[i]+=SUM[i-1];
l=1; r=1; q[1]=0;
for(int i=1;i<=N;i++){
while(l+1<=r&&dy(q[l+1],q[l])<=SUM[i]*dx(q[l+1],q[l])) l++;
DP[i]=DP[q[l]]+(SUM[i]-SUM[q[l]])*(SUM[i]-SUM[q[l]])+M;
while(l+1<=r&&dy(i,q[r])*dx(q[r],q[r-1])<=dy(q[r],q[r-1])*dx(i,q[r])) r--;
q[++r]=i;
}
printf("%d\n",DP[N]);
}
return 0;
}