P16531 [THUPC 2026 决赛] 棋盘对弈游戏

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）决赛。 题解等资源可在 https://github.com/dapingguo8/THUPC2026-final 查看。 > 在单人操作的积木消除小游戏后，小 T 和小 S 还准备了一项双人互动的棋盘对弈小游戏。 > > 游戏在一套特制的十周年纪念棋盘上进行。棋盘上面分布着带有分值的格子，参与的双方需要轮流控制棋子向前跳跃，抢占格子上的分数，以最大化自己和对手分数的差值。

这套特制的棋盘由 $n$ 个格子组成，其中格子 $i \ (3 \le i \le n)$ 的分值为 **正整数** $a_k$。 你决定与你的队友进行一场对弈。游戏开始时，你占据了格子 $1$ 并放上了自己的棋子，而你的队友占据了格子 $2$ 并放上了他的棋子，且此时仅有这两个格子被占据。双方的初始得分均为零。 游戏由你率先行动，之后双方轮流进行。在每个回合中，设当前行动玩家的棋子位于格子 $x$，则该玩家必须选择一个步数 $d \in \{1, 2, 3, 4\}$，满足 $x + d \le n$，且格子 $x + d$ **尚未被占据**，然后将自己的得分加上该格子对应的分值 $a_{x + d}$，并将其棋子向前跳跃至格子 $x + d$。跳跃完成后，该玩家将占据这一新格子（请注意，该玩家之前占据的格子会一直被这一玩家占据）。特别地，若不存在任何合法的跳跃步数，该玩家本回合将无法行动并直接跳过。当双方均无法行动时，游戏结束，可以证明游戏一定会在有限步内结束。 显然，擅长博弈的你和你的队友都足够聪明，均会在对弈中采取最优策略。为了提前推演对局结果，你需要计算出在游戏结束时，你的总得分减去你的队友的总得分的值。

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 $T \ (1 \le T \le 10 ^ 3)$，表示数据组数。对于每组测试数据： - 第一行包含一个正整数 $n \ (6 \le n \le 10 ^ 5)$，表示棋盘的格子数量。 - 第二行包含 $n - 2$ 个正整数 $a_3, a_4, \dots, a_n \ (1 \le a_k \le 10 ^ 9)$，分别表示每个格子的分值。 保证所有测试数据中 $n$ 的和不超过 $10 ^ 5$。

对于每组测试数据，输出一行一个整数，表示你的总得分减去你的队友的总得分的值。

以下用一个长度为 $n$ 的字符串表示对局结果，其中字符 `.` 表示该格子未被任何人占据，字符 `O` 表示该格子被你占据，字符 `X` 表示该格子被你的队友占据。 对于第一组测试数据，在第一次行动中，你有以下三种选择： - 选择步数 $d = 2$，将棋子跳跃至格子 $3$，则对局结果为 `OXOXXO`，得分差为 $-6$； - 选择步数 $d = 3$，将棋子跳跃至格子 $4$，则对局结果为 `OX.OOX`，得分差为 $5$； - 选择步数 $d = 4$，将棋子跳跃至格子 $5$，则对局结果为 `OX..OX`，得分差为 $-1$。 因此对局结果为 `OX.OOX`，得分差为 $5$。 对于第二组测试数据，一种可能的对局结果为 `OXOXOXOX`，得分差为 $0$。 对于第三组测试数据，一种可能的对局结果为 `OX..OXOOOX`，得分差为 $-7$。 对于第四组测试数据，一种可能的对局结果为 `OX..OXXXO`，得分差为 $8$。 对于第五组测试数据，一种可能的对局结果为 `OXXXOXOO`，得分差为 $90$。 对于第六组测试数据，一种可能的对局结果为 `OX..OXO.XO`，得分差为 $1000000000$。