ARC116F Deque Game

题意 ： 给出 个序列，第 个序列 的长度为 。

A 和 B 用这些序列玩游戏，两人轮流进行下列操作，直到所有序列的长度都变为 。

• 删除某个（长度至少为 的）序列的开头或结尾。

A 先手。A 想要最大化最终剩下的 个元素的和，而 B 想要最小化，求最终这 个元素的和。

，时限 。

---

先观察只有一个序列的情况。

记 为 的答案。

• ，B 先手：。

• ，A 先手：。

• ，B 先手：。

• ，A 先手：。

如此不难归纳证明：

• 为偶数，A 先手时， 。

• 为奇数，B 先手时， 。

由于 和 对称，先后手反过来也类似：

• 为偶数，B 先手时， 。

• 为奇数，A 先手时， 。

---

准备工作：比较对于一个序列，先手赚还是后手赚。

• 为偶数：双方都是先手更赚。

• 为奇数：双方都是后手更赚。

  因为前者至多是 ，后者至少是 。

接着我们来研究多个序列的情况，可以归纳证明：

• 若所有 均为奇数，先手操作一次后，会形成一个偶序列，则后手必定接着操作这个偶序列。

  答案即为各个序列的答案的和。

• 若存在偶序列，则先手必选一个偶序列操作。

  这可以说明两人必定先瓜分完偶序列，然后变为奇数序列的情况。

  注意瓜分完之后先后手可能会变化。

  对于第 个序列，记操作一次后的 的较大值（要考虑先后手）为 ，较小值为 。

  若让 A 操作，则会选 ，B 选 。按照 从大到小排序，按这个顺序瓜分。