LibreOJ 10190. 「APIO2010」特别行动队

首先列出朴素的转移方程 $f_{i} = max_{0 \leq j < i} (f_{j} + a (s u m_{i} - s u m_{j})^{2} + b (s u m_{i} - s u m_{j}) + c)$ 。
其中 $s u m_{i} = \sum_{j = 1}^{i} x_{j}$ 。

对于 $0 \leq k < j < i$ ，假设决策 $j$ 优于决策 $k$ ，有

\begin{aligned} f_{j} + a (s u m_{i} - s u m_{j})^{2} + b (s u m_{i} - s u m_{j}) + c & \geq f_{k} + a (s u m_{i} - s u m_{k})^{2} + b (s u m_{i} - s u m_{k}) + c \\ f_{j} - 2 a \cdot s u m_{i} s u m_{j} + a \cdot s u m_{j}^{2} - b \cdot s u m_{j} & \geq f_{k} - 2 a \cdot s u m_{i} s u m_{k} + a \cdot s u m_{k}^{2} - b \cdot s u m_{k} \\ (f_{j} + a \cdot s u m_{j}^{2} - b \cdot s u m_{j}) - (f_{k} + a \cdot s u m_{k}^{2} - b \cdot s u m_{k}) & \geq 2 a \cdot s u m_{i} (s u m_{j} - s u m_{k}) \\ \frac{(f_{j} + a \cdot s u m_{j}^{2} - b \cdot s u m_{j}) - (f_{k} + a \cdot s u m_{k}^{2} - b \cdot s u m_{k})}{s u m_{j} - s u m_{k}} & \geq 2 a \cdot s u m_{i} \end{aligned}

维护一只上凸包即可~

代码：

#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]);
}

『My guiding star.』

LibreOJ 10190 「APIO2010」特别行动队