#P18906. [2026多校联测]game

[2026多校联测]game

题目描述

有 nn 堆石子排成一排,从左到右第 ii 堆有 aia_i 个石子。

两个人轮流操作,每次操作必须从以下三种中选择一种执行:

  • 合并相邻的两堆石子,变成一堆,石子数为两堆之和;
  • 丢掉目前最靠左的一堆石子;
  • 丢掉目前最靠右的一堆石子。

一直操作到只剩下一堆石子为止。

其中一个人希望最后剩下的那堆石子尽量少,另一个人希望尽量多,两人都足够聪明(都采取最优策略)。

给定 nn 和先手的人是谁,求最后剩下的那堆石子的数量。

输入格式

第一行两个整数 n,kn,k。其中 k∈{0,1}k\in\{0,1\}:k=0k=0 表示希望最后尽量少的人先手,k=1k=1 表示希望尽量多的人先手。

第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n。

输出格式

一行一个整数,表示最后剩下的那堆石子的数量。

样例 1

2 0
1 2
1

样例 2

3 1
1 2 3
3

样例 3

5 0
1 2 3 4 5
6

样例解释

  • 样例 1:希望尽量少的人先手,他丢掉最靠右的一堆,剩下 11。
  • 样例 2:希望尽量多的人先手,他把第 1,21,2 堆合并成一堆 33,局面变成两堆 3,33,3,之后无论对方丢掉哪一堆,剩下的都是 33。
  • 样例 3:答案为 66。此时最后一步由希望尽量多的人执行,他能保证最后剩下的那一堆是原来某个连续 33 堆的合并结果,其中最小的是 1+2+3=61+2+3=6。

子任务

测试点编号 约束 分值
1-9 n≤20n\le20 20
10-13 n≤105n\le10^5,每堆石子大小相等
14-17 n≤105n\le10^5,nn 是偶数且希望尽量多的人先手
18-21 n≤105n\le10^5,nn 是偶数且希望尽量少的人先手
22-31 n≤2000n\le2000 5
32-41 n≤105n\le10^5 15

对于 100%100\% 的数据,1≤n≤1051\le n\le10^5,0≤k≤10\le k\le1,1≤ai1\le a_i,且 ∑i=1nai≤109\sum_{i=1}^{n}a_i\le10^9。