1949:数组魔法阵
文件提交:无需freopen
内存限制:128 MB
时间限制:1.000 S
评测方式:普通裁判
命题人:
提交:7
解决:3
题目描述
在蒜头王国的魔法学院里,蒜头君发现了一项古老的魔法试验——"极光之选"。这项试验要求利用一个充满魔力的数组,通过精心挑选出 $k$ 段特定长度的子数组,来汇聚最大的魔法能量,点亮整个魔法阵。现在,蒜头君诚邀你一同参与这顶激动人心的挑战!
你面前摆放着一个由 $n$ 个魔力值组成的数组,每个元素代表着该位置的魔力强度。你的任务是选择 $k$ 段长度均为 $m$ 的连续子数组(这些子数组互不重叠),每段子数组的魔力值之和将被累积,以期达到最大累积魔力值,从而激活 “极光之选” 的终极魔法。
你的魔法任务是运用你的智慧,设计一种策略,选取 $k$ 段长度为 $m$ 的魔力值数组,使得这些子数组的魔力值之和最大化。计算并告知蒜头君,通过最优选择,所能达到的最大累积魔力值是多少。
注意:
- 数组长度 $n$ 与子数组长度 $m$ 均符合实际魔法操作的限制。
- 确保所选的每段子数组互不重叠,即任意两段子数组之间没有共同的元素。
输入
第一行包含三个整数 $n,m,k$
第二行包含 $n$ 个整数,代表魔力值数组的魔力值。
$1\le (m\times k)\le n\le 3000$,魔力值在 int 范围内且为正整数。
输出
输出最终的要求答案。
样例输入-1 复制
5 2 1
1 2 3 4 5
样例输出-1 复制
9
样例输入-2 复制
7 1 3
2 10 7 18 5 33 0
样例输出-2 复制
61