[AGC026F] Manju Game

题解

为了方便描述结论,把输入的数组看作 \(n\) 个格子,每个格子里填了一个数字。对格子黑白染色,第一个格子是黑色,相邻两个格子颜色不同。

不难发现结论:如果 \(n\) 为偶数,先手最优策略得到的收益是黑格子上数字的和与白格子上数字的和的最大值。如果 \(n\) 为奇数,设白格子上数字的和为 \(s\),先手能够获得至少 \(x\) 的收益,当且仅当存在一种选出若干个白格子的方案,用这些白格子把 \(n\) 个格子分成若干个连续段,每个连续段内黑格子的和减去白格子的和都大于等于 \(x-s\)

证明比较显然,具体过程不写出了。大概思路就是要证明先手最优策略的收益是 \(x\),只需先手存在一种策略,无论后手怎么操作至少能够 \(x\) 的收益,后手存在一种策略无论先手怎么操作一定能使先手获得至多 \(x\) 的收益。\(n\) 为奇数直接做,\(n\) 为偶数二分 dp 一下即可。

代码

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
#include <bits/stdc++.h>

using namespace std;

const int maxn = 300010;

int n, a[maxn], sum[maxn];

int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
if (n & 1) {
int L = -1e9, R = 1e9, ans = 0, s = 0;
for (int i = 1; i <= n; i++) if (i & 1) sum[i] = sum[i-1] + a[i]; else sum[i] = sum[i-1] - a[i];
while (L <= R) {
int mid = (L + R) >> 1;
int mns = 0;
for (int i = 1; i < n; i += 2) {
if (sum[i] - mns >= mid) {
mns = min(mns, sum[i+1]);
}
}
if (sum[n] - mns >= mid) {
L = mid + 1;
ans = mid;
} else R = mid-1;
}
for (int i = 2; i <= n; i += 2) ans += a[i];
for (int i = 1; i <= n; i++) s += a[i];
printf("%d %d\n", ans, s - ans);
} else {
int s0 = 0, s1 = 0;
for (int i = 1; i <= n; i++) if (i & 1) s1 += a[i]; else s0 += a[i];
if (s0 < s1) swap(s0, s1);
printf("%d %d\n", s0, s1);
}
return 0;
}