dp[i] = dp[j] + (a[i] - a[j])^2 + m;
展开得 dp[i] = min{dp[j] + a[i]^2 + a[j]^2 - 2*a[i]*a[j] + m}
其中a[i]^2 是与i相关的变量， 而m是常量，所以可以从表达式中抽离出来
所以只要求 dp[i] = min{dp[j] + a[j]^2 + 2*a[i]*a[j]} 即可，
设k = a[i] , x = 2*a[j]， y = dp[j] + a[j]^2，G = dp[i]
那么就是G = -kx + y,
为了得到dp[i]的最小值， 那么需要枚举j，那么相当于二维的坐标系上有很多个点，
然后有一条斜率为-k的直线从y轴下方无限远处慢慢向上平移， 直到经过坐标系上的一个点，
那么此时与y轴的截距G是最小的，
我们只要维护一个凸包就行了。
设红线的斜率为k，直线ab的斜率为kab,
如果k<kab, 那么点a就是最优的，因为如果要经过点a之后的点，就必须把红线往上平移
如果k>kab, 那么点a不是最优的，因为如果要经过点b，是把红线往下移，也就是说点a是可以舍弃的，因为k=a[i],
而a[i]是递增不减的，所以说点a是当前可舍弃，以后也可舍弃的
至于k==kab, 那么点a也是可舍弃的
为什么不在凸包上的点就不可能成为最优点呢？
因为t不在凸包上，所以ktb < kat
如果t可以成为最优的，那么就是说存在一条斜率为k的直线
使得k>=kat且 k<ktb, 然而ktb < kat, 所以这是不可能发生的事情，所以舍弃掉
所以我们就是维护一个凸包就行啦。
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <functional>
#include <map>
#include <set>
using namespace std;
typedef long long LL;
const int INF = <<;
/*
* */
const int N = + ;
int a[N];
int dp[N];
int q[N],head,tail;
int n,m;
int getUp(int k1, int k2)
{
return (dp[k1]+a[k1]*a[k1]) - (dp[k2]+a[k2]*a[k2]);
}
int getDown(int k1, int k2)
{
return a[k1] - a[k2];
}
int getDp(int i, int k)
{
return dp[k] + (a[i] - a[k]) * (a[i] - a[k]) + m;
}
int main()
{
//freopen("/Users/whoami/in.txt","r",stdin);
while(scanf("%d%d",&n,&m)!=EOF)
{
memset(dp,,sizeof(dp));
for(int i=;i<=n;++i)
{
scanf("%d",&a[i]);
a[i] += a[i-];
}
head = tail = ;
q[tail++] = ;
for(int i=;i<=n;++i)
{
/*
while(head+1<tail && getDp(i,q[head])<=getDp(i,q[head+1]))
head++;
*/
//得到最优值
while(head+<tail && getUp(q[head+], q[head])<= * a[i] * getDown(q[head+], q[head]))
head++;
dp[i] = getDp(i,q[head]);
//维护下凸包,
while(head+<tail && getUp(q[tail-],q[tail-])*getDown(i,q[tail-]) >= getUp(i,q[tail-])*getDown(q[tail-],q[tail-]))
tail--;
q[tail++] = i; }
printf("%d\n",dp[n]);
}
return ;
}