CF2140C.Ultimate Value

我们定义一个函数 $f(a)$，对于长度为 $n$ 的数组 $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$ 的值；这会令 $\textrm{cost}$ 增加 $(r - l)$。

假设 Alice 总是试图最大化 $f(a)$，而 Bob 试图最小化 $f(a)$。

你的任务是，假设双方都采取最优策略时，输出最后的 $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)$。

对于第一个测试用例，Alice 在自己的第一步就选择终止游戏是最优策略。

此时 $\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$。

由 ChatGPT 5 翻译