← 返回题目列表

Codeforces · 2140/C

C. 终极价值

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

让我们为长度为 $$$n$$$ 的数组 $$$a$$$ 定义一个函数 $$$f(a)$$$ 为 $$f(a) = \textrm{cost} + (a_1 - a_2 + a_3 - a_4 \cdots a_n)$$,其中 $$$\textrm{cost}$$$ 最初为零。

现在考虑这样的场景:给 Alice 和 Bob 一个长度为 $$$n$$$ 的数组 $$$a$$$。他们轮流玩最多 $$$10^{100}$$$ 回合的游戏,Alice 先玩。

在每个回合中,他们必须执行任何 一 (仅一项)以下操作:

  • 结束 Alice 和 Bob 的游戏。
  • 选择两个索引 $$$l,r$$$ 和 $$$1 \le l \le r \le n$$$ 并交换 $$$a_l$$$ 和 $$$a_r$$$;这会将 $$$(r - l)$$$ 添加到 $$$\textrm{cost}$$$ 中。

假设 Alice 尝试最大化 $$$f(a)$$$ 而 Bob 尝试最小化它。

你的任务是假设两个玩家都发挥最佳状态,确定 $$$f(a)$$$ 的最终值。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) — 数组 $$$a$$$ 的长度。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,a_3,\ldots,a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 数组 $$$a$$$ 的元素。

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

输出

对于每个测试用例,输出一个整数 - $$$f(a)$$$ 的最终值(假设两个玩家都处于最佳状态)。

示例

输入
复制

5
2
1000 1
5
9 9 9 9 9
4
7 1 8 4
6
1 14 1 14 1 15
9
31 12 14 22 89 6 78 25 91

输出
复制

999
13
12
-7
265

注意

对于第一个测试用例,爱丽丝最好在第一回合结束游戏。

因此 $$$\textrm{cost} = 0$$$ 和 $$$f(a) = 0 + 1000 - 1 = 999$$$ 的最终值。

对于第四个测试用例,Alice 最好交换 $$$a_1$$$ 和 $$$a_6$$$,然后 Bob 在第一回合结束游戏是最优的。

因此 $$$\textrm{cost} = 5$$$ 和 $$$f(a) = 5 + 15 - 14 + 1 - 14 + 1 - 1=-7$$$ 的最终值。