斜率优化
特别行动队
思路
先上个前缀和，设 $d[i]$ 表示“前 $i$ 个数能得到的最大值”，转移为：
$$
d[i] = \max(d[j] + a(s[i] - s[j])^2 + b(s[i] - s[j]) + c)
$$
显然斜率优化，化式子，考虑 $j$ 优于 $k$ 的条件：
$$
\begin{aligned}
d[j] + a(s[i] - s[j])^2 + b(s[i] - s[j]) + c &> d[k] + a(s[i] - s[k])^2 + b(s[i] - s[k]) + c \\
d[j] + as[i]^2 - 2as[i]s[j] + as[j]^2 + bs[i] - bs[j] + c &> d[k] + as[i]^2 - 2as[i]s[k] + as[k]^2 + bs[i] - bs[k] + c \\
d[j] - 2as[i]s[j] + as[j]^2 - bs[j] &> d[k] - 2as[i]s[k] + as[k]^2 - bs[k] \\
\frac{(d[j] + as[j]^2 - bs[j]) - (d[k] + as[k]^2 - bs[k])}{s[j] - s[k]} &> 2as[i]
\end{aligned}
$$
显然维护斜率递增即可，考虑到 $X(t) = s[t]$ ， $K(t) = 2as[t]$ 都是单调的，直接上单调队列即可
代码
太久没打了，调了半天
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| #include <bits/stdc++.h>
using LL = long long;
const int N = 1e6 + 100;
int n, a, b, c, s[N], q[N], l, r;
LL d[N];
LL X(int x){ return s[x]; }
LL Y(int x){ return d[x] + LL(a) * s[x] * s[x] - LL(b) * s[x]; }
LL K(int x){ return 2ll * a * s[x]; }
int main()
{
scanf("%d %d %d %d", &n, &a, &b, &c);
for (int i = 1; i <= n; ++i) scanf("%d", &s[i]);
for (int i = 2; i <= n; ++i) s[i] += s[i - 1];
q[l = r = 1] = 0;
for (int i = 1; i <= n; ++i)
{
while (l < r && (Y(q[l + 1]) - Y(q[l])) > (X(q[l + 1]) - X(q[l])) * K(i)) ++l;
if (l <= r) d[i] = d[q[l]] + LL(s[i] - s[q[l]]) * (s[i] - s[q[l]]) * a + LL(s[i] - s[q[l]]) * b + c;
while (l < r && (Y(q[r]) - Y(q[r - 1])) * (X(i) - X(q[r])) <= (Y(i) - Y(q[r])) * (X(q[r]) - X(q[r - 1]))) --r;
q[++r] = i;
}
printf("%lld\n", d[n]);
return 0;
}
|