0%

[ABC162F] Select Half

题目

题目链接

题目大意:给出长度为 $n$ 的序列,要求选 $\lfloor\frac{n}{2}\rfloor$ 个不相邻的数使得选出的数的和最大。 $2 \le n \le 2 \times 10^5, |a_i| \le 10^9$。

思路

如果没有个数限制,可以用 $f(i, j)(j \in \{0, 1\})$ 表示取或不取第 $i$ 个数时的最大收益。

但是这道题有个数上的限制。

考虑偶数的情况,显然答案只有两种可能,取或不取第一个数。

但是奇数的情况就不一样了,我们发现可能有两个数之间隔了两个数的情况存在,但这也不一定存在。

考虑 DP,设 $f_i$ 表示取到第 $i$ 个数时的最大收益($i > 1$),$s_i$ 为隔了一个数得到的前缀和。

首先考虑第一个取不取,显然,$f_2 = \max(a_2, a_1)$。

然后考虑第二个取不取,则 $f_3 = \max(f_1 + a_3, f_2)$。

同样得到 $f_4 = \max(f_2 + a_4, s_3)$。

则状态转移方程:

感觉这道题的状态转移方程还是挺难想的。

代码

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
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return;
}

typedef long long LL;

LL a[200010], f[200010], sum[200010];
LL n;

int main() {
read(n);
for (int i = 1; i <= n; ++i) read(a[i]);
sum[1] = a[1];
for (int i = 2; i <= n; ++i) sum[i] = sum[i - 2] + a[i];
for (int i = 2; i <= n; ++i) {
if (i & 1) {
f[i] = std::max(f[i - 1], f[i - 2] + a[i]);
} else {
f[i] = std::max(f[i - 2] + a[i], sum[i - 1]);
}
}
printf("%lld\n", f[n]);
return 0;
}