https://codeforces.com/problemset/problem/1555/C
Alice and Bob are playing a game on a matrix, consisting of 2 rows and 𝑚 columns. The cell in the 𝑖-th row in the 𝑗-th column contains 𝑎𝑖,𝑗 coins in it.
Initially, both Alice and Bob are standing in a cell (1,1). They are going to perform a sequence of moves to reach a cell (2,𝑚).
The possible moves are:
Move right — from some cell (𝑥,𝑦) to (𝑥,𝑦+1);
Move down — from some cell (𝑥,𝑦) to (𝑥+1,𝑦).
First, Alice makes all her moves until she reaches (2,𝑚). She collects the coins in all cells she visit (including the starting cell).
When Alice finishes, Bob starts his journey. He also performs the moves to reach (2,𝑚) and collects the coins in all cells that he visited, but Alice didn't.
The score of the game is the total number of coins Bob collects.
Alice wants to minimize the score. Bob wants to maximize the score. What will the score of the game be if both players play optimally?
Input
The first line contains a single integer 𝑡 (1≤𝑡≤104) — the number of testcases.
Then the descriptions of 𝑡 testcases follow.
The first line of the testcase contains a single integer 𝑚 (1≤𝑚≤105) — the number of columns of the matrix.
The 𝑖-th of the next 2 lines contain 𝑚 integers 𝑎𝑖,1,𝑎𝑖,2,…,𝑎𝑖,𝑚 (1≤𝑎𝑖,𝑗≤104) — the number of coins in the cell in the 𝑖-th row in the 𝑗-th column of the matrix.
The sum of 𝑚 over all testcases doesn't exceed 105.
Output
For each testcase print a single integer — the score of the game if both players play optimally.
Example
input
3
3
1 3 7
3 5 1
3
1 3 9
3 5 1
1
4
7
output
7
8
0
Note
The paths for the testcases are shown on the following pictures. Alice's path is depicted in red and Bob's path is depicted in blue.
- 脑筋急转弯
- 前缀和/后缀和
- 枚举
- 暂无
要做出这道题，需要明确两点。
- 由于不能向上和向左，因此如果一旦选择向下移动，那么就不可能再向上了，否则无法到达终点。
- 由提示 1 可知， Alice 一定是在 j ( 0 <= j < m)列向下移动并且收集第二行的满足列 i <= j < m 的硬币，且总共收集了 m + 1 个硬币。
对于 bob 来说，只能选择：
- 第一行中 alice 没有选择的部分，我们不妨记为 first
- 第二行中 alice 没有选择的部分，我们不妨记为 second
由前面的提示，我们知道 bob 只能选择其中一个。
因此我们可以枚举 alice 的拐点，计算 first，second 中的较大值进行选择。
其中选择较大值是 bob 的最优策略。而 alice 的最优策略是选择合适的拐点，让 bob 的最优策略最差。
- 枚举拐点
- 语言支持：Python3
Python3 Code:
t = int(input())
for _ in range(t):
input()
A = list(map(int, input().split(" ")))
B = list(map(int, input().split(" ")))
first = sum(A[1:])
second = 0
ans = float("inf")
for i in range(len(A)):
ans = min(ans, max(first, second))
if i + 1 < len(A):
first -= A[i + 1]
second += B[i]
print(ans)
复杂度分析
令 n 为数组长度。
- 时间复杂度：$O(n)$
- 空间复杂度：$O(1)$