[APIO2010] 特别行动队

Description

给定长度为 (n) 的数列，将其分成若干份，每份的权值为 $ax^2 + bx + c $，其中 (x) 为该份的和。最大化权值总和。

Solution

设 (f[i]) 表示前 (i) 个数经过若干次划分能得到的最大权值，则有

[f[i] = max_j f[j] + a(s[i]-s[j])^2 + b(s[i]-s[j]) + c ]

(b) 项的总和是一个定值，先将它分出去，剩余部分经过变形得到

[f[j]+acdot s^2[j] = 2a cdot s[i]s[j] + f[i]-acdot s^2 [i] -c ]

以 (s[j]) 为 (x)，以 (f[j]+acdot s^2[j]) 为 (y)，每次询问的斜率为 (2acdot s[i])，维护单调递增的下凸包

#include <bits/stdc++.h>
using namespace std;

#define int long long 
const int N = 1000005;

int n,s[N],f[N],a,b,c;
int q[N],head=0,tail=0;

int getx(int j)
{
    return s[j];
}

int gety(int j)
{
    return f[j]+a*s[j]*s[j];
}

int getk(int i)
{
    return 2*a*s[i];
}

int getfi(int i,int val)
{
    return val+a*s[i]*s[i]+c;
}

double slope(int i,int j)
{
    return 1.0*(gety(i)-gety(j))/(getx(i)-getx(j));
}

signed main()
{
    ios::sync_with_stdio(false);

    cin>>n;

    cin>>a>>b>>c;
    
    int ans=0;

    for(int i=1;i<=n;i++) cin>>s[i];
    for(int i=1;i<=n;i++) s[i]+=s[i-1];

    for(int i=1;i<=n;i++)
    {
        while(head<tail && slope(q[head],q[head+1])>getk(i)) ++head;
        int j=q[head];
        f[i]=getfi(i, gety(j)-getk(i)*getx(j));
        while(head<tail && slope(i,q[tail])>slope(q[tail-1],q[tail])) --tail;
        q[++tail]=i;
    }


    cout<<f[n]+b*s[n]<<endl;
}