102703: [AtCoder]ABC270 D - Stones
Description
Score : $400$ points
Problem Statement
Takahashi and Aoki will play a game of taking stones using a sequence $(A_1, \ldots, A_K)$.
There is a pile that initially contains $N$ stones. The two players will alternately perform the following operation, with Takahashi going first.
- Choose an $A_i$ that is at most the current number of stones in the pile. Remove $A_i$ stones from the pile.
The game ends when the pile has no stones.
If both players attempt to maximize the total number of stones they remove before the end of the game, how many stones will Takahashi remove?
Constraints
- $1 \leq N \leq 10^4$
- $1 \leq K \leq 100$
- $1 = A_1 < A_2 < \ldots < A_K \leq N$
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_K$
Output
Print the answer.
Sample Input 1
10 2 1 4
Sample Output 1
5
Below is one possible progression of the game.
- Takahashi removes $4$ stones from the pile.
- Aoki removes $4$ stones from the pile.
- Takahashi removes $1$ stone from the pile.
- Aoki removes $1$ stone from the pile.
In this case, Takahashi removes $5$ stones. There is no way for him to remove $6$ or more stones, so this is the maximum.
Below is another possible progression of the game where Takahashi removes $5$ stones.
- Takahashi removes $1$ stone from the pile.
- Aoki removes $4$ stones from the pile.
- Takahashi removes $4$ stones from the pile.
- Aoki removes $1$ stone from the pile.
Sample Input 2
11 4 1 2 3 6
Sample Output 2
8
Below is one possible progression of the game.
- Takahashi removes $6$ stones.
- Aoki removes $3$ stones.
- Takahashi removes $2$ stones.
In this case, Takahashi removes $8$ stones. There is no way for him to remove $9$ or more stones, so this is the maximum.
Sample Input 3
10000 10 1 2 4 8 16 32 64 128 256 512
Sample Output 3
5136
Input
题意翻译
#### 题目翻译 Takahashi 和 Aoki 在玩一个取石子的游戏。 刚开始，有 $N$ 个石子，还有一个长度为 $K$ 的序列 $A = \{A_1,A_2,\cdots,A_K\}$。 现在，他们要按照以下规则轮流取石子： * 对于每次操作，他可以选择一个 $i$（$1 \leq i \leq K$），这时他会取走 $A_i$ 块石子。 * 当一个人没法取石子时，游戏结束。 现在，Takahashi 先取石子，Aoki 后取石子。 他们都想尽可能的最大化他们自己取走的石子数量。 若他们都以最优策略取石子，最后 Takahashi 会取走多少块石子？ #### 输入格式 第一行两个正整数 $N, K$ 第二行有 $K$ 个正整数，其中第 $i$ 个表示 $A_i$ #### 输出格式 一行一个正整数，表示若他们都以最优策略取石子，最后 Takahashi 取走的石子数量。 #### 数据范围 对于 $100\%$ 的数据，保证： * $1 \leq N \leq 10^4$ * $1 \leq K \leq 100$ * $1 = A_1 < A_2 < \cdots < A_K \leq N$Output
分数：400分
问题描述
高桥和青木将使用序列$(A_1, \ldots, A_K)$进行取石游戏。
最初有一个包含$N$颗石头的堆。两人将交替执行以下操作，高桥先开始。
- 选择一个不超过当前堆中石头数量的$A_i$。从堆中移除$A_i$颗石头。
当堆中没有石头时，游戏结束。
如果双方都试图在游戏结束前最大化他们移除的石头总数，那么高桥将移除多少颗石头？
约束条件
- $1 \leq N \leq 10^4$
- $1 \leq K \leq 100$
- $1 = A_1 < A_2 < \ldots < A_K \leq N$
- 输入中的所有值都是整数。
输入
输入将从标准输入以以下格式给出：
$N$ $K$ $A_1$ $A_2$ $\ldots$ $A_K$
输出
打印答案。
样例输入1
10 2 1 4
样例输出1
5
以下是游戏可能进行的一种方式。
- 高桥从堆中移除了4颗石头。
- 青木从堆中移除了4颗石头。
- 高桥从堆中移除了1颗石头。
- 青木从堆中移除了1颗石头。
在这种情况下，高桥移除了5颗石头。他无法移除6颗或更多的石头，因此这是最大值。
以下是另一种高桥移除5颗石头的游戏可能进行的方式。
- 高桥从堆中移除了1颗石头。
- 青木从堆中移除了4颗石头。
- 高桥从堆中移除了4颗石头。
- 青木从堆中移除了1颗石头。
样例输入2
11 4 1 2 3 6
样例输出2
8
以下是游戏可能进行的一种方式。
- 高桥移除了6颗石头。
- 青木移除了3颗石头。
- 高桥移除了2颗石头。
在这种情况下，高桥移除了8颗石头。他无法移除9颗或更多的石头，因此这是最大值。
样例输入3
10000 10 1 2 4 8 16 32 64 128 256 512
样例输出3
5136