题目描述

Description

Input

Output

Sample Input

4
-1 10 -20
2 2 3 4 

Sample Output

9

HINT

题目分析

列出方程：
设f[i]表示前i个士兵的战斗力之和的最大值。
那么有f[i]=f[j]+a*(sum[i]-sum[j])^2+b*(sum[i]-sum[j])+c，
其中sum为前缀和。
展开平方，整理得f[j]+a*sum[j]^2-b*sum[j]=2*a*sum[i]*sum[j]+f[i]-a*sum[i]^2-b*sum[i]-c
因为这题要求最大值 于是维护一个上凸包即可，与下凸包的差别就在于斜率比较时'>'和'<'的不同。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
long long s[1000100],v[1000100],f[1000100],a,b,c;
int q[1000100],l,r,n;
long long yi(int i) { return f[i]+a*s[i]*s[i]-b*s[i]; }
long long xi(int i) { return s[i]; } 
int main()
{
    scanf("%d%lld%lld%lld",&n,&a,&b,&c);
    for(int i=1;i<=n;i++) scanf("%lld",&v[i]);
    for(int i=1;i<=n;i++) s[i]=s[i-1]+v[i];
    for(int i=1;i<=n;i++)
    {
        while(l<r&&yi(q[l+1])-yi(q[l])>2*a*s[i]*(xi(q[l+1])-xi(q[l]))) l++;
        f[i]=f[q[l]]+a*(s[i]-s[q[l]])*(s[i]-s[q[l]])+b*(s[i]-s[q[l]])+c;
        while(l<r&&(yi(i)-yi(q[r]))*(xi(q[r])-xi(q[r-1]))>(yi(q[r])-yi(q[r-1]))*(xi(i)-xi(q[r]))) r--;
        q[++r]=i;
    }
    printf("%lld",f[n]);
    return 0;
}