Description

题库链接

给你一个长度为 \(n\) 的序列 \(x\)，你可以把这份序列划分为任意多份。如果某一份的 \(x\) 的和为 \(X\)，那么这一份的价值为 \(aX^2+bX+c\)。问你划分后得到的最大价值为多少。

\(1\leq n\leq 10^6,-5\leq a\leq -1,|b,c|\leq 10^7,1\leq x_i\leq 100\)

Solution

设 \(f_i\) 为 \(1\sim i\) 划分后得到的最大价值。

我们对序列 \(x\) 做一个前缀和 \(s\)，那么 \(f_i=\min\limits_{1\leq j<i}\{f_j+a(s_i-s_j)^2+b(s_i-s_j)+c\}\)。

把后面的式子完全拆开 \(f_i=f_j+as_i^2-2as_is_j+as_j^2+bs_i-bs_j+c\)，等价于 \(2as_is_j+f_i=f_j+as_i^2+as_j^2+bs_i-bs_j+c\)。

这是一个含 \(i,j\) 和 \(ij\) 项的式子，并且 \(2as_i\) 与 \(s_j\) 单调性相反，因此是可以斜率优化的。

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e6+5;

int n, x[N], a, b, c, q[N], head, tail;
ll f[N];

ll caly(int i) {return 1ll*a*x[i]*x[i]-1ll*b*x[i]+f[i]; }
int main() {
    scanf("%d%d%d%d", &n, &a, &b, &c);
    for (int i = 1; i <= n; i++)
        scanf("%d", &x[i]), x[i] += x[i-1];
    q[0] = 0;
    for (int i = 1; i <= n; i++) {
        while (head < tail && caly(q[head+1])-caly(q[head]) >= 2ll*a*x[i]*(x[q[head+1]]-x[q[head]])) ++head;
        f[i] = f[q[head]]+1ll*a*(x[i]-x[q[head]])*(x[i]-x[q[head]])+1ll*b*(x[i]-x[q[head]])+c;
        while (head < tail && (caly(q[tail])-caly(i))*(x[q[tail-1]]-x[i]) >= (caly(q[tail-1])-caly(i))*(x[q[tail]]-x[i]))
            --tail;
        q[++tail] = i;
    }
    printf("%lld\n", f[n]);
    return 0;
}