#216563. [THUPC 2026 决赛] 棋盘对弈游戏

来自 2026 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2026）决赛。

题解等资源可在 https://github.com/dapingguo8/THUPC2026-final 查看。

这套特制的棋盘由 个格子组成，其中格子 的分值为 正整数 。

你决定与你的队友进行一场对弈。游戏开始时，你占据了格子 并放上了自己的棋子，而你的队友占据了格子 并放上了他的棋子，且此时仅有这两个格子被占据。双方的初始得分均为零。

游戏由你率先行动，之后双方轮流进行。在每个回合中，设当前行动玩家的棋子位于格子 ，则该玩家必须选择一个步数 ，满足 ，且格子 尚未被占据，然后将自己的得分加上该格子对应的分值 ，并将其棋子向前跳跃至格子 。跳跃完成后，该玩家将占据这一新格子（请注意，该玩家之前占据的格子会一直被这一玩家占据）。特别地，若不存在任何合法的跳跃步数，该玩家本回合将无法行动并直接跳过。当双方均无法行动时，游戏结束，可以证明游戏一定会在有限步内结束。

显然，擅长博弈的你和你的队友都足够聪明，均会在对弈中采取最优策略。为了提前推演对局结果，你需要计算出在游戏结束时，你的总得分减去你的队友的总得分的值。

每个测试点中包含多组测试数据。输入的第一行包含一个正整数 ，表示数据组数。对于每组测试数据：

• 第一行包含一个正整数 ，表示棋盘的格子数量。
• 第二行包含 个正整数 ，分别表示每个格子的分值。

保证所有测试数据中 的和不超过 。

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

样例输入 1

6
6
1 6 3 4
10
1 1 1 1 1 1 1 1
10
1 1 1 1 1 1 1 10
9
1 1 1 1 1 1 10
8
10 1 1 1 1 100
10
1000000000 1 1000000000 1 1000000000 1 1000000000 1

样例输出 1

5
0
-7
8
90
1000000000

样例输入 2

6
9
7 6 2 2 5 8 7
10
8 26 18 1 11 9 15 9
11
8 3 9 2 3 4 8 8 7
12
5 6 5 3 1 2 1 1 5 4
15
6 6 7 2 2 2 5 2 2 4 7 7 7
18
7 4 5 1 2 6 7 5 7 3 7 3 6 5 6 6

样例输出 2

5
13
8
3
9
9

以下用一个长度为 的字符串表示对局结果，其中字符 . 表示该格子未被任何人占据，字符 O 表示该格子被你占据，字符 X 表示该格子被你的队友占据。

对于第一组测试数据，在第一次行动中，你有以下三种选择：

• 选择步数 ，将棋子跳跃至格子 ，则对局结果为 OXOXXO，得分差为 ；
• 选择步数 ，将棋子跳跃至格子 ，则对局结果为 OX.OOX，得分差为 ；
• 选择步数 ，将棋子跳跃至格子 ，则对局结果为 OX..OX，得分差为 。

因此对局结果为 OX.OOX，得分差为 。

对于第二组测试数据，一种可能的对局结果为 OXOXOXOX，得分差为 。

对于第三组测试数据，一种可能的对局结果为 OX..OXOOOX，得分差为 。

对于第四组测试数据，一种可能的对局结果为 OX..OXXXO，得分差为 。

对于第五组测试数据，一种可能的对局结果为 OXXXOXOO，得分差为 。

对于第六组测试数据，一种可能的对局结果为 OX..OXO.XO，得分差为 。