开始: 2026-10-18 12:00:00

【集训13】DP与优化

结束: 2026-10-24 00:00:00
当前  2026-11-04 11:35:09  类型: IOI  状态: 已经结束 

P5. 连续实习期
描述

某公司 n 天有值班任务,第 i 天的**报酬**是 p_i。

员工可以报名若干个**连续的实习期**:每个实习期恰好覆盖**连续的 m 天**,报酬就是这 m 天报酬之和。要求:

- 一共报名**恰好 k 个**实习期;

- 任意两个实习期**不能有任何一天重叠**;

- 一天最多属于一个实习期(不参加的天没有报酬)。

问能拿到的**报酬总和最大值**。


输入

第一行**三个整数 n、m、k**(注意顺序:先每段长度 m,再段数 k)。

第二行 n 个整数 p_i。

输出

一行一个整数:k 段互不重叠的长度为 m 的连续区间之和的最大值。末尾换行。


样例

输入

5 2 1
1 2 3 4 5

输出

9

输入

7 1 3
2 10 7 18 5 33 0

输出

61
提示

**样例 #1 解释**

每段长 m=2、只选 k=1 段。长度 2 的区间和依次是 3,5,7,9,最大是第 4,5 天这段,4+5=9。

**样例 #2 解释**

m=1(每段只有 1 天)、k=3(挑 3 天),取最大的三个 33+18+10=61。

| t1 | 20 | 20 | 3\le n\le8, 1\le m\le3, 1\le k\le3 | 

| t2 | 20 | 40 | 14\le n\le18, 1\le m\le4, 2\le k\le5 |

| t3 | 20 | 60 | 30\le n\le36, 1\le m\le4, 4\le k\le12 |

| t4 | 20 | 80 | 800\le n\le1000, 1\le m\le5, 8\le k\le40 | 

| t5 | 20 | 100 | n=5000, p_i\le10^9(约每 4 组一次 m=1 且 k 接近 n) | 

提交

题目参数
时间限制 1 秒
内存限制 512 MB
提交