C. Ultimate Value

问题

我们为长度为 $n$ 的数组 $a$ 定义一个函数 $f(a)$ 如下 $f(a) = \text{cost} + (a_1 - a_2 + a_3 - a_4 + \ldots + a_n)$ 其中 cost 初始为零。

现在考虑一个场景，Alice 和 Bob 得到了一个长度为 $n$ 的数组 $a$。他们轮流进行游戏，最多进行 $10^{100}$ 轮，Alice 先手。

在每一轮中，他们必须执行以下操作之一（仅一个）：

1. 结束 Alice 和 Bob 的游戏。
2. 选择两个索引 $l, r$，$1 \leq l \leq r \leq n$，并交换 $a_l$ 和 $a_r$；这将向 cost 中增加 $(r - l)$。

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

你的任务是确定在双方都以最优方式游戏的情况下，$f(a)$ 的最终值。

题解与观察

解决这个问题的关键洞察来自于结合两个因素：索引位置及其相关的交换成本。

1. 游戏简化：

   • 游戏实际上可以简化为寻找一次最优的交换，因为 Alice 总能撤销 Bob 的移动。

2. 关键策略 - 索引-成本组合：

   • 对于位置 $i$ 的每个元素，我们考虑：
     • 交换的成本（取决于位置 $i$）
     • 如果我们移动这个元素，值的变化
   • 通过结合这些因素，我们可以评估每个潜在移动的总影响。
   • 我们分别跟踪奇数和偶数位置上可达到的最佳差值。

3. 最终值： 答案是以下各项的最大值：

   • 初始的交替和（没有任何交换）
   • 在考虑了所有可能的索引-成本组合后可达到的最佳值。

该解决方案结合了动态规划和对不同位置交换可能产生的值变化的仔细跟踪。

提交链接