暴力做法

我们首先来推下这道题普通的 DP 方程，显而易见，维护前缀和后，在\(f[i]\)时枚举一个点\(j\)划分即可：

\[ f[i] = max_{j\in [1,i-1]} \{f[j]+a(S[i]-S[j])^2+b(S[i]-S[j])+c\} \]

时间复杂度为\(O(n^2)\)，GG。

斜率优化分析

第一步 – 写出斜率方程

这是所有斜率优化题目分析的第一步：给定两个量\(j_1<j_2\)，写出斜率不等式得出单调关系。这一步进行参变分离即可，稍稍有点麻烦。

我们以本题为例，进行斜率方程的推导：

\[ f[j_1]+a(S[i]-S[j_1])^2+b(S[i]-S[j_1])+c>f[j_2]+a(S[i]-S[j_2])^2+b(S[i]-S[j_2])+c \\ (f[j_1]-f[j_2])+a(S[j_1]^2-S[j_2]^2)+b(S[j_2]-S[j_1])>2a(S[j_1]-S[j_2])*S[i] \\ \frac{(f[j_1]-f[j_2])+a(S[j_1]^2-S[j_2]^2)+b(S[j_2]-S[j_1])}{2a(S[j_1]-*S[j_2])}>S[i] \]

注意\(a<0\)。

第二步 – 队头的弹出条件

我们观察这个方程，当\(j_2\)比\(j_1\)更优时：

\[ \frac{(f[j_1]-f[j_2])+a(S[j_1]^2-S[j_2]^2)+b(S[j_2]-S[j_1])}{2a(S[j_1]-S[j_2])} \leq S[i] \]

因为\(S[i]\)随着\(i\)单调不下降，所以当\(j_2\)比\(j_1\)更优时，\(j_1\)永远不会被考虑，弹出。

第三步 – 队头转移

这个没什么好说的，直接将\(q[head]\)当做\(j\)来用即可。

第四步 – 队尾的处理

我们还需要保证这些直线斜率的单调性。首先，以本题为例，我们来对斜率单调性进行分析。

我们假设斜率函数为\(slope(j_1,j_2)\)，函数的解析式就是我们上面推出来的式子，即：

\[ slope(j_1, j_2) = \frac{(f[j_1]-f[j_2])+a(S[j_1]^2-S[j_2]^2)+b(S[j_2]-S[j_1])}{2a(S[j_1]-S[j_2])} \]

我们假设直线的斜率必须要单调递增，也就是\(l<mid<r, slope(l,mid)<slope(mid,r)\)。我们在单调队列中只保留可能成为最优解的选项，也就是对于元素\(a_1,a_2,a_3\)，\(a_1\)比\(a_2\)更优且\(a_2\)比\(a_3\)更优。所以，中间我们有：

\[ slope(l,mid)>S[i] \text{且} slope(mid,r)<S[i] \]

整理得：

\[ slope(l,mid)>slope(mid,r) \]

与假设相反。所以，我们处理队尾的时候其实就是在维护这个关系，所以弹出条件就是“如果这个斜率是单调递增的”：

\[ l<mid<r, slope(l,mid)<slope(mid,r) \]

所以，分析完毕。

代码

// P3628.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX_N = 1e6 + 2000;
ll n, xi[MAX_N], a, b, c, S[MAX_N], f[MAX_N], q[MAX_N], head, tail;
ll pow(ll num) { return num * num; }
double slope(int j1, int j2)
{
    return double((f[j1] - f[j2] + b * (S[j2] - S[j1]) + a * (pow(S[j1]) - pow(S[j2])))) / double(2 * a * (S[j1] - S[j2]));
}
int main()
{
    scanf("%lld%lld%lld%lld", &n, &a, &b, &c);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &xi[i]), S[i] = S[i - 1] + xi[i];
    head = 1, tail = 1;
    for (int i = 1; i <= n; i++)
    {
        while (head < tail && slope(q[head], q[head + 1]) <= S[i] * 1.0)
            head++;
        f[i] = f[q[head]] + a * pow(S[i] - S[q[head]]) + b * (S[i] - S[q[head]]) + c;
        while (head <= tail && slope(q[tail - 1], q[tail]) >= slope(q[tail], i))
            tail--;
        q[++tail] = i;
    }
    printf("%lld", f[n]);
    return 0;
}