hdu3507 경사율 최적화 dp

#include<iostream>
#include<vector>
#include<string>
#include<queue>
#include<map>
#include<cstdio>
#include<cstring>
#define maxn 500005
#define INF 0xfffffff
#define min(a,b) a<b?a:b
#define max(a,b) a>b?a:b
using namespace std;
int n,m,head,tail;
int sum[maxn],q[maxn],dp[maxn];
int getUp(int i,int j)
{
    return dp[i]+sum[i]*sum[i]-dp[j]-sum[j]*sum[j];
}
int getDown(int i,int j)
{
    return 2*sum[i]-2*sum[j];
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        sum[0]=dp[0]=0;//          0
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&sum[i]);
            sum[i]=sum[i-1]+sum[i];
        }
        head=tail=0;
        q[tail++]=0;// 0  ，         2  
        for(int i=1;i<=n;i++)
        {
            while(head+1<tail&&getUp(q[head+1],q[head])<=sum[i]*getDown(q[head+1],q[head]))//        g[j,k]<=sum[i]
            head++;
            dp[i]=dp[q[head]]+m+(sum[i]-sum[q[head]])*(sum[i]-sum[q[head]]);

            while(head+1<tail&&getUp(i,q[tail-1])*getDown(q[tail-1],q[tail-2])<=getUp(q[tail-1],q[tail-2])*getDown(i,q[tail-1]))//         g[i,j]<=g[j,k]         
            tail--;
            q[tail++]=i;
        }
        printf("%d
",dp[n]);
    }
	return 0;
}