CF1389B Array Walk

给定一个由 $n$ 个正整数组成的数组 $a_1, a_2, \dots, a_n$。 你最初站在下标为 $1$ 的位置，初始得分为 $a_1$。你可以进行两种操作： 1. 向右移动——从当前位置 $x$ 移动到 $x+1$，并将 $a_{x+1}$ 加入你的得分。仅当 $x < n$ 时可以执行此操作。 2. 向左移动——从当前位置 $x$ 移动到 $x-1$，并将 $a_{x-1}$ 加入你的得分。仅当 $x > 1$ 时可以执行此操作。此外，不能连续两次或以上向左移动。 你需要恰好进行 $k$ 次移动，并且其中向左移动的次数不超过 $z$ 次。 你能获得的最大得分是多少？

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含三个整数 $n, k, z$（$2 \le n \le 10^5$，$1 \le k \le n-1$，$0 \le z \le \min(5, k)$），分别表示数组的长度、需要进行的总移动次数以及最多允许向左移动的次数。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^4$），表示给定的数组。 所有测试用例中 $n$ 的总和不超过 $3 \times 10^5$。

输出 $t$ 行，每行一个整数，表示对于每个测试用例，在恰好进行 $k$ 次移动、且向左移动次数不超过 $z$ 且不能连续两次或以上向左移动的情况下，所能获得的最大得分。

在第一个测试用例中，不允许向左移动。因此你只能向右移动四次，得分为 $a_1 + a_2 + a_3 + a_4 + a_5$。 在第二个测试用例中，你可以向左移动一次。可以按如下顺序移动：右、右、左、右。得分为 $a_1 + a_2 + a_3 + a_2 + a_3$。 在第三个测试用例中，虽然最多可以向左移动四次，但最优策略依然是向右移动四次，得分为 $a_1 + a_2 + a_3 + a_4 + a_5$。 由 ChatGPT 4.1 翻译