斜率优化的练手题
通读题目可以发现
$$
f_i=\max (f_j+g(s[i]-s[j]))
$$
$$
其中f_i表示在i处强制结束一段的最大代价,s_i表示a_i的前缀和,g(x)表示(ax^2+bx+c)
$$
展开这个式子我们得到
$$
f_i=\max(f_j+as_i^2-2as_is_j+as_j^2+bs_i-bs_j+c)
$$
去掉$\max$，移项得到:
$$
(f_j+as_j^2-bs_j)=2as_is_j+(f_i-as_i^2-bs_i-c)
$$
然后就是常规的单调队列维护上凸壳了
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
| #include <bits/stdc++.h>
#define R register
#define ll long long
#define sum(a, b, mod) (((a) + (b)) % mod)
const int MaxN = 1e6 + 10;
ll n, A, B, C;
ll a[MaxN], s[MaxN], f[MaxN], q[MaxN];
inline ll read()
{
ll x = 0, f = 1;
char ch = getchar();
while (ch > '9' || ch < '0')
{
if (ch == '-')
f = 0;
ch = getchar();
}
while (ch <= '9' && ch >= '0')
x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
return f ? x : (-x);
}
ll g(int num) { return A * num * num + B * num + C; }
ll x(int num) { return s[num]; }
ll y(int num) { return (f[num] + A * s[num] * s[num] - B * s[num]); }
ll k(int num) { return 2 * A * s[num]; }
int main()
{
n = read(), A = read(), B = read(), C = read();
for (int i = 1; i <= n; i++)
a[i] = read(), s[i] = s[i - 1] + a[i];
int l = 1, r = 1;
for (int i = 1; i <= n; i++)
{
while (l < r && (y(q[l + 1]) - y(q[l])) >= k(i) * (x(q[l + 1]) - x(q[l])))
++l;
f[i] = f[q[l]] + g(s[i] - s[q[l]]);
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", f[n]);
return 0;
}
|