#P18906. [2026多校联测]game
[2026多校联测]game
题目描述
有 堆石子排成一排,从左到右第 堆有 个石子。
两个人轮流操作,每次操作必须从以下三种中选择一种执行:
- 合并相邻的两堆石子,变成一堆,石子数为两堆之和;
- 丢掉目前最靠左的一堆石子;
- 丢掉目前最靠右的一堆石子。
一直操作到只剩下一堆石子为止。
其中一个人希望最后剩下的那堆石子尽量少,另一个人希望尽量多,两人都足够聪明(都采取最优策略)。
给定 和先手的人是谁,求最后剩下的那堆石子的数量。
输入格式
第一行两个整数 。其中 : 表示希望最后尽量少的人先手, 表示希望尽量多的人先手。
第二行 个整数 。
输出格式
一行一个整数,表示最后剩下的那堆石子的数量。
样例 1
2 0
1 2
1
样例 2
3 1
1 2 3
3
样例 3
5 0
1 2 3 4 5
6
样例解释
- 样例 1:希望尽量少的人先手,他丢掉最靠右的一堆,剩下 。
- 样例 2:希望尽量多的人先手,他把第 堆合并成一堆 ,局面变成两堆 ,之后无论对方丢掉哪一堆,剩下的都是 。
- 样例 3:答案为 。此时最后一步由希望尽量多的人执行,他能保证最后剩下的那一堆是原来某个连续 堆的合并结果,其中最小的是 。
子任务
| 测试点编号 | 约束 | 分值 |
|---|---|---|
| 1-9 | 20 | |
| 10-13 | ,每堆石子大小相等 | |
| 14-17 | , 是偶数且希望尽量多的人先手 | |
| 18-21 | , 是偶数且希望尽量少的人先手 | |
| 22-31 | 5 | |
| 32-41 | 15 |
对于 的数据,,,,且 。