数组行走 - 代码源竞赛平台

题目描述

蜗蜗站在一个由 $n$ 个正整数组成的数组的第 $1$ 个位置，初始得分为 $a_1$。

每一步，他可以向右移动一格，或向左移动一格，并把到达位置的数加入得分。移动时不能走出数组；他不能连续两步向左移动。

蜗蜗必须恰好移动 $k$ 步，其中向左移动的次数至多为 $z$。求最终得分的最大值。

输入格式

第一行包含一个整数 $t$，表示测试用例数。

对于每组测试用例，第一行包含三个整数 $n,k,z$，第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对于每组测试用例，输出一行一个整数，表示恰好移动 $k$ 步后的最大得分。

样例

2
5 4 1
1 5 4 3 2
3 2 0
4 1 9

19
14

1
2 1 1
7 8

15

样例解释

样例 1 的第一组数据可以按“右、右、左、右”移动，依次获得 $1,5,4,5,4$，总分为 $19$。第二组数据不能向左移动，只能得到 $4+1+9=14$ 分。

样例 2 中，只能向右移动一步，得分为 $7+8=15$。

数据范围

对于 100% 的数据，保证 $1\le t\le 10^4$，$2\le n\le 10^5$，$1\le k\le n-1$，$0\le z\le\min(5,k)$，$1\le a_i\le 10^4$；同一输入中所有测试用例的 $n$ 之和不超过 $3\times 10^5$。