题解

思路推导

设实际向左移动 $l$ 次。每次向左之后若还要继续移动，下一步必须向右，因此这些左右往返可以集中在已经到达的某一对相邻位置上。完成 $k$ 次移动后的最终下标为 $k-2l+1$（按题面的一基下标）。

固定 $l$ 后，路径必然至少收集前 $k-2l+1$ 个位置各一次；每次左右往返会额外收集某一对相邻位置各一次。为了最大化得分，应选择可到达范围内元素和最大的相邻对重复 $l$ 次。

做法

预处理数组前缀和。枚举 $0\le l\le z$ 且 $2l\le k$，令 $r=k-2l$ 为最终零基下标。计算前缀 $a_0+\cdots+a_r$，并在 $0\le p\le r$ 的相邻对 $(a_p,a_{p+1})$ 中取最大和。候选答案是前缀和加 $l$ 倍最大相邻对和，取所有 $l$ 的最大值。

正确性证明

固定向左次数 $l$。去掉每次向左及紧随其后的向右，这些成对操作不改变最终位置，剩余 $k-2l$ 次移动只能全部向右，因此基础路径恰好贡献前缀 $a_0$ 到 $a_{k-2l}$。

每对被去掉的左右操作都发生在基础路径能够到达的一条相邻边上，并额外贡献这条边两个端点的值。把所有往返安排在其中端点和最大的边上合法，且不比任何分散安排更差。因此该 $l$ 下公式给出最优值。

枚举全部合法 $l$ 后覆盖所有可行路径，取最大值即为全局最优答案。

复杂度分析

每组只枚举至多 $z+1\le6$ 种向左次数，并扫描所需前缀，时间复杂度为 $O(kz)$，空间复杂度为 $O(n)$。