学步园

初学斜率优化……

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define maxn 500005
int sum[maxn];
int dp[maxn];
int a[maxn];
int q[maxn];
int y(int i)
{
    return dp[i]+sum[i]*sum[i];
}
int Gup(int j,int k)
{
    return y(j)-y(k);
}
int Gdown(int j,int k)
{
    return sum[j]-sum[k];
}
inline int ReadInt()        //开挂，刷一下排行
{
    char ch = getchar();
    int data = 0;
    while (ch < '0' || ch > '9')
    {
        ch = getchar();
    }
    do
    {
        data = data*10 + ch-'0';
        ch = getchar();
    }while (ch >= '0' && ch <= '9');
        return data;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        sum[0]=0;
        for(int i=1;i<=n;i++){
            a[i]=ReadInt();
            sum[i]=sum[i-1]+a[i];
        }
        int head=0,tail=-1;
        q[++tail]=0;
        for(int i=1;i<=n;i++)
        {
            while(head<tail&&Gup(q[head+1],q[head])<=2*sum[i]*Gdown(q[head+1],q[head])) head++;
            dp[i]=dp[q[head]]+(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]])+m;
            while(head<tail&&Gup(i,q[tail])*Gdown(q[tail],q[tail-1])<=Gup(q[tail],q[tail-1])*Gdown(i,q[tail]))
            tail--;
            q[++tail]=i;
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}