LibreOJ 10190 「APIO2010」特别行动队

首先列出朴素的转移方程 fi=max0≤j<i(fj+a(sumi−sumj)2+b(sumi−sumj)+c)。
其中 sumi=i∑j=1xj。

对于 0≤k<j<i，假设决策 j 优于决策 k，有 fj+a(sumi−sumj)2+b(sumi−sumj)+c≥fk+a(sumi−sumk)2+b(sumi−sumk)+cfj−2a⋅sumisumj+a⋅sum2j−b⋅sumj≥fk−2a⋅sumisumk+a⋅sum2k−b⋅sumk(fj+a⋅sum2j−b⋅sumj)−(fk+a⋅sum2k−b⋅sumk)≥2a⋅sumi(sumj−sumk)(fj+a⋅sum2j−b⋅sumj)−(fk+a⋅sum2k−b⋅sumk)sumj−sumk≥2a⋅sumi

维护一只上凸包即可~

代码：

#include <cstdio>
using namespace std;
const int N = 1e6;
int n,a,b,c;
int q[N + 5],head,tail;
long long f[N + 5],sum[N + 5];
inline double slope(int x,int y)
{
    return (double)(f[x] - f[y] + (sum[x] * sum[x] - sum[y] * sum[y]) * a - (sum[x] - sum[y]) * b) / (sum[x] - sum[y]);
}
int main()
{
    scanf("%d%d%d%d",&n,&a,&b,&c);
    for(register int i = 1;i <= n;++i)
        scanf("%lld",sum + i),sum[i] += sum[i - 1];
    q[head = tail = 1] = 0;
    for(register int i = 1;i <= n;++i)
    {
        for(;head < tail && slope(q[head],q[head + 1]) >= 2 * a * sum[i];++head);
        f[i] = f[q[head]] + a * (sum[i] - sum[q[head]]) * (sum[i] - sum[q[head]]) + b * (sum[i] - sum[q[head]]) + c;
        for(;head < tail && slope(q[tail - 1],q[tail]) <= slope(q[tail],i);--tail);
        q[++tail] = i;
    }
    printf("%lld\n",f[n]);
}