3748: 跳跃(第四轮02)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：3
解决：1
题目描述
crying 在梦里也希望和 Mio 贴贴，但是 Mio 不理她，所以她一个人在梦里玩 跳房子。（好奇怪）
游戏场地是一个一行 n 个格子的序列 a，每个格子都各自有一个权值，第 i 个 格子的权值为 ai，注意 ai 可能非正。
crying 一开始站在 1 处，并且面向右侧。然后她会进行 k 次跳跃。
每次跳跃，crying 可以向她的方向跳任意步（也可以不跳）， 然后转身（也就是 说，如果她向右跳， 那么下次跳跃应该向左； 反之， 应该向右）。设她开始在第 x个格子，跳跃到了第 y 个格子，则 crying 的得分累加上第 x 个格子到第 y 个格子之间的所有格子的权值之和（包括第 x 个格子和第 y 个格子）。注意在 整个 k 次跳跃过程中， crying 不能跳出序列 a。
一开始 crying 的得分为 0，任意时刻， crying 的权值都必须是非负的。
试求出至多 k 次跳跃（可能为 0）后， crying 可以得到的最大的得分。
输入
第一行一个正整数 T，表示数据组数。
对于每一组数据，第一行两个整数 n, k，分别代表格子长度，和 crying 的最多 跳跃次数。
接下来一行 n 个整数，依次代表 a1 , a2 , … , an 。
输出
对于每一组数据， 一行一个整数， 代表 crying 进行至多 k 次跳跃后， 能得到 的最大分数。
样例输入 复制
2
3 4
10 -100 80
15 400000000
-100 1 2 3 4 5 6 7 8 9 10 11 12 13 14样例输出 复制
90
41999999900提示
【样例 1 输入】
2
3 4
10 -100 80
15 400000000
-100 1 2 3 4 5 6 7 8 9 10 11 12 13 14
【样例 1 输出】
90
41999999900
【样例 1 说明】
第一次跳跃：向右跳。注意到若从 1 跳到 2，则得分变为 0 + (10) + (−100) = −90，为负，不符合题意， 同理不能从 1 跳到 3， 所以只能从 1 跳 0 步， 还 是待在 1，分数变为 0 + (10) = 100 + (10) = 10。
第二次跳跃：向左跳。发现 1 的左边没有格子了，所以还是只能待在 1，分数变
为 10 + (10) = 20。
第三次跳跃：向右跳。从 1 直接跳到 3，分数变为 20 + (10) + (−100) + (80) = 10。
第四次跳跃：向左跳。从 3 跳到 3（原地不动），分数变为 10 + (80) = 90。
容易发现， 90 就是 crying 进行至多 4 次跳跃可以获得的最大得分。
【数据范围】
对于 20% 的数据， n, k ≤ 10
对于 50% 的数据， n, k ≤ 1000
对于 100% 的数据， 1 ≤ T ≤ 10,0 ≤∣ ai ∣≤ 10^5, 1 ≤ n ≤ 1000,0 ≤ k ≤ 10^9
2
3 4
10 -100 80
15 400000000
-100 1 2 3 4 5 6 7 8 9 10 11 12 13 14
【样例 1 输出】
90
41999999900
【样例 1 说明】
第一次跳跃：向右跳。注意到若从 1 跳到 2，则得分变为 0 + (10) + (−100) = −90，为负，不符合题意， 同理不能从 1 跳到 3， 所以只能从 1 跳 0 步， 还 是待在 1，分数变为 0 + (10) = 100 + (10) = 10。
第二次跳跃：向左跳。发现 1 的左边没有格子了，所以还是只能待在 1，分数变
为 10 + (10) = 20。
第三次跳跃：向右跳。从 1 直接跳到 3，分数变为 20 + (10) + (−100) + (80) = 10。
第四次跳跃：向左跳。从 3 跳到 3（原地不动），分数变为 10 + (80) = 90。
容易发现， 90 就是 crying 进行至多 4 次跳跃可以获得的最大得分。
【数据范围】
对于 20% 的数据， n, k ≤ 10
对于 50% 的数据， n, k ≤ 1000
对于 100% 的数据， 1 ≤ T ≤ 10,0 ≤∣ ai ∣≤ 10^5, 1 ≤ n ≤ 1000,0 ≤ k ≤ 10^9