hdu 3507 Print Article 斜率優化DP

/*
    dp[i]為寫i個字符最小花費
    dp[i]=min(dp[i],dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])+m);
    dp[i]=min(dp[i],dp[k]+(sum[i]-sum[k])*(sum[i]-sum[k])+m);
    設取j時優於k，k<j
    ==>dp[j]+(sum[i]-sum[j])*(sum[i]-sum[j])>=dp[k]+(sum[i]-sum[k])*(sum[i]-sum[k])+草稿紙

    ==>[(dp[j]+sum[j]*sum[j])-(dp[k]+sum[k]*sum[k])] / 2(sum[j]-sum[k]) <=sum[i]

    ==>G[j,k]=(yj-yk)/(xj-xk)<=2*sum[i];

    [做題的時候看成- - - >(yj-yk)<=2*sum[i]*(xj-xk);防止除法]

    即滿足上述條件的時候，k<j，否則k>j;
    當g[k,j]>g[j,i]的時候 j可以被去掉（就是上凸點，證明可以分g[j,i]<sum[i]和>sum[i]討論）
*/
#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++)
        {
                    //head這還好
            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;    //dp方程
                    //tail注意這裡有分母有大小關系啊，乘過去要變號啊，WA死我了啊
            while(head<tail&&Gup(i,q[tail])*Gdown(q[tail],q[tail-1])<=Gup(q[tail],q[tail-1])*Gdown(i,q[tail]))
                  //k<j<i  ==> tail,tail-1,i;
            tail--;
            q[++tail]=i;
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}