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，kdp[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);防止除法]

    即满足上述条件的时候，kj;
    当g[k,j]>g[j,i]的时候 j可以被去掉（就是上凸点，证明可以分g[j,i]sum[i]讨论）
*/
#include
#include
#include
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,tail-1,i;
            tail--;
            q[++tail]=i;
        }
        printf("%d\n",dp[n]);
    }
    return 0;
}