[APIO 2010] 特别行动队

题目大意

nn 个士兵,初始战斗力为 xix_i。先分为几段作为特别行动队(每段编号连续),每段的初始战斗力为 x=i[l,  r]xix = \sum_{i \in [l, \; r]} x_i,之后再处理为 x=Ax2+Bx+Cx' = A x^2 + B x + C。求最大的战斗力。

1n1,000,0001 \leqslant n \leqslant 1,000,000

1xi1001\leqslant x_i \leqslant 100

5A1-5 \leqslant A \leqslant -1

B,  C10,000,000|B|, \; |C| \leqslant 10,000,000

题目链接

【APIO 2010】特别行动队

题解

DP + 斜率优化。

f[i]f[i] 为前 ii 个的答案,则转移为:

f[i]=max(f[j]+A(X[i]X[j])2+B(X[i]X[j])+C)j[1,  i1]f[i] = max(f[j] + A (X[i] - X[j])^2 + B (X[i] - X[j]) + C) \quad j \in [1, \; i - 1]

其中 XXxix_i 的前缀和。

对于后面的一堆,考虑两个决策点 aabba>ba > b),假设 aa 优于 bb,有:

\begin{align} f[a] + A(X[i] - X[a])^2 + B(X[i] - X[a]) + C &> f[b] + A(X[i] - X[b])^2\\ &+ B(X[i] - X[b]) + C \\ f[a] + A X[a]^2 - 2 A X[i] X[a] - B X[a] &> f[b] + A X[b]^2\\ &- 2 A X[i] X[b] - B X[b] \\ \frac{(f[a] + A X[a]^2 - B X[a]) - (f[b] + A X[b]^2 - B X[b])}{X[a] - X[b]} &> 2 A X[i] \end{align}

用斜率的单调队列维护决策点,最优决策点在一个上凸包上。

代码

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
#include <cstdio>
const int MAXN = 1000005;
long long f[MAXN];
long long x[MAXN], pSumX[MAXN], a, b, c;
long long y(int i) {
return f[i] + a * pSumX[i] * pSumX[i] - b * pSumX[i];
}
double slope(int i, int j) {
return (double) (y(i) - y(j)) / (pSumX[i] - pSumX[j]);
}
int n;
void dp() {
static int q[MAXN];
int *l = q, *r = q;
for (int i = 1; i <= n; i++) {
while (l < r && slope(*l, *(l + 1)) > 2 * a * pSumX[i]) l++;
int k = *l;
long long temp = pSumX[i] - pSumX[k];
f[i] = f[k] + a * temp * temp + b * temp + c;
while (l < r && slope(*(r - 1), *r) < slope(*r, i)) r--;
*++r = i;
}
}
int main() {
scanf("%d %lld %lld %lld", &n, &a, &b, &c);
for (int i = 1; i <= n; i++) scanf("%lld", &x[i]);
for (int i = 1; i <= n; i++) pSumX[i] = pSumX[i - 1] + x[i];
dp();
printf("%lld\n", f[n]);
return 0;
}