#D. 蒜头君的数组魔法阵

    传统题 1000ms 256MiB

蒜头君的数组魔法阵

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

在蒜头王国的魔法学院里,蒜头君发现了一项古老的魔法实验——“极光之选”。这项试验要求利用一个充满魔力的数组,通过精心挑选出k段特定长度的子数组,来汇聚最大的魔法能力,电亮整个魔法阵。现在,蒜头君诚邀你一同参与这项激动人心的挑战!

你面前摆放着一个由n个魔力值组成的数组,每个元素代表着该位置的魔力强度。你的任务是选择k段长度均为m的连续子数组(这些子数组互不重叠),每段子数组的魔力值之和将被雷击,以期达到最大的累积魔力值,从而激活“极光之选”的终极魔法。

你的魔法任务是运用你的智慧,设计一种策略,选取k段长度为m的魔力数组,使得这些子数组的魔力值之和最大化。计算并告知蒜头君,通过最优选择,所能达到的最大累积魔力值是多少。

注意:

1.数组长度n与子数组长度m均符合实际魔法操作的限制。

2.确保所选的每段子数组互不重叠,即任意两段子数组之间没有共同的元素。

输入格式

第一行包含三个整数n和m和k。

第二行包含n个整数,代表魔力值数组的魔力值。

输出格式

输出最终的要求答案

数据范围

对于40%的数据,1mkn5001\leq{m*k}\leq{n}\leq500,魔力值在int范围内且为正整数;

对于100%的数据,1mkn50001\leq{m*k}\leq{n}\leq5000,魔力值在int范围内且为正整数;

样例

5 2 1
1 2 3 4 5
9
样例解释1

按题意,选取一段连续两个元素组成使其最大,我们选取最后两个元素即可,答案为9

7 1 3
2 10 7 18 5 33 0
61

Limitation

1000ms,262144K

8.12模拟赛

未参加
状态
已结束
规则
OI
题目
4
开始于
2024-8-12 8:30
结束于
2024-8-12 12:30
持续时间
4 小时
主持人
参赛人数
24