← 返回题目列表

Codeforces · 2215/D

D. 探索、利用并获得一些经验!

中文机器翻译题面 查看原题

几年后,Shiro 和 White 都进入了 THU。在课堂上了解了“多臂强盗”问题的EXP3算法后,他们突然突发奇想,设计了一个与此无关的游戏。

有$$$n$$$个位置排成一排,从前到后编号为$$$1,2,\ldots,n$$$。每个位置可以处于两种状态之一: 变黑 or 未黑化。白棋的棋子从位置 $$$1$$$ 开始,白棋的棋子从位置 $$$2$$$ 开始。游戏开始时,只有 $$$1$$$ 和 $$$2$$$ 位置 变黑.

玩家轮流出手,白先走。在每个回合中,当前玩家必须选择自己的棋子,然后向前跳 $$$1$$$ 到 $$$4$$$ 步,到达下一个棋子。 未黑化 位置,以及 变黑 他们降落的位置。如果玩家无法进行合法的移动(即 $$$1$$$ 到 $$$4$$$ 范围内的所有位置,从当前位置向前迈出的步数要么超出 $$$n$$$,要么已经 变黑),玩家将跳过本回合(即不移动)。

游戏结束时 两者 白和白无法做出任何有效的动作。很容易证明游戏保证在有限步数内终止。

对于每个 $$$3\le k\le n$$$,位置 $$$k$$$ 有一个 积极 整数权重$$$a_k$$$。每当有玩家 变黑 这样的位置$$$k$$$,他们的分数增加了$$$a_k$$$。白和白一开始的得分都是$$$0$$$,他们的目标都是在比赛结束时最大化自己和对手得分之间的差距。

令$$$d=s_1 - s_2$$$,其中$$$s_1$$$是Shiro的分数,$$$s_2$$$是White的分数。 Shiro和White想知道:如果双方都按照最优策略行动,游戏结束后$$$d$$$的价值是多少?由于这个问题太复杂,他们从 THUSAA 转向你。你必须帮助他们解决问题。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 1000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$6\le n\le 10^5$$$) — 位置数。

第二行包含 $$$n-2$$$ 整数 $$$a_3, a_4, \ldots, a_n$$$ ($$$1\le a_i\le 10^9$$$) — 头寸 $$$3$$$ 到 $$$n$$$ 的权重。

保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。

输出

对于每个测试用例,输出一个整数 - $$$d$$$ 的最终值。

示例

输入
复制

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

输出
复制

5
0
-7
8
90
1000000000

输入
复制

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

输出
复制

5
13
8
3
9
9

注意

以下是第一个示例测试的说明:

我们使用字符 O 表示没有人访问过的位置, S 表示 Shiro 访问过的位置,以及 W 表示白方走过的位置。然后,最终的配置可以用长度为 $$$n-2$$$ 的字符串表示,并且该字符串唯一对应于两个玩家的移动顺序。

对于第一个测试用例,考虑 Shiro 的第一步作为起始玩家:

  • 她无法移动到位置$$$2$$$,因为该位置已经被白棋占据;
  • 如果她的第一步是$$$3$$$,那么最终状态是 SWWS (分数差为$$$-6$$$);
  • 如果她的第一步是走$$$4$$$位置,那么最终状态是 OSSW (分数差为$$$5$$$);
  • 如果她的第一步是$$$5$$$,那么最终状态是 OOSW (分数差为$$$-1$$$);

因此,最佳最终状态是 OSSW,得分差异为 $$$5$$$。

对于第二个测试用例,一种可能的最终状态是 SWSWSWSW,得分差异为 $$$0$$$。

对于第三个测试用例,白棋可以在两步棋中获得最远的位置 $$$10$$$,而 Shiro 无法到达。因此,白棋的一种可能策略是向前大幅推进,以防止白棋进一步拖延。对应的最终状态为 OOSWSSSW,得分差异为 $$$-7$$$。

对于第四个测试用例,一种可能的最终状态是 OOSWWWW,得分差异为 $$$8$$$。

对于第五个测试用例,一种可能的最终状态是 WWSWSS,得分差异为 $$$90$$$。

对于第六个测试用例,一种可能的最终状态是 OOSWSOWS,分数差异为 $$$1\,000\,000\,000$$$。