George and Job
题意翻译
# 题目描述
新款手机 iTone6 近期上市,George 很想买一只。不幸地,George 没有足够的钱,所以 George 打算当一名程序猿去打工。现在George遇到了一个问题。
给出一组有 $n$ 个整数的数列 $p_1,p_2,...,p_n$ ,你需要挑出 $k$ 组长度为 $m$ 的数,要求这些数互不重叠
即$ [l_{1},r_{1}],[l_{2},r_{2}],...,[l_{k},r_{k}] (1<=l_{1}<=r_{1}<l_{2}<=r_{2}<...<l_{k}<=r_{k}<=n; r_{i}-l_{i}+1=m)$
使选出的数的和值最大,请你帮助George码出这份代码
# 输入输出格式
## 输入格式
第1行读入3个整数 $n , m , k(1\leq(m×k)\leq n\leq5000) (1\leq(m×k)\leq n\leq5000)$,
第2行读入 $n$ 个数 $p_1,p_2,...,p_n$
## 输出格式
输出1个整数,代表可以取到的最大值
# 输入输出样例
如原版
translated by @Venus
题目描述
The new ITone 6 has been released recently and George got really keen to buy it. Unfortunately, he didn't have enough money, so George was going to work as a programmer. Now he faced the following problem at the work.
Given a sequence of $ n $ integers $ p_{1},p_{2},...,p_{n} $ . You are to choose $ k $ pairs of integers:
$ [l_{1},r_{1}],[l_{2},r_{2}],...,[l_{k},r_{k}] (1<=l_{1}<=r_{1}<l_{2}<=r_{2}<...<l_{k}<=r_{k}<=n; r_{i}-l_{i}+1=m), $ in such a way that the value of sum ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF467C/f485241e7e91a377aee475847d196e97e051c6c5.png) is maximal possible. Help George to cope with the task.
输入输出格式
输入格式
The first line contains three integers $ n $ , $ m $ and $ k $ $ (1<=(m×k)<=n<=5000) $ . The second line contains $ n $ integers $ p_{1},p_{2},...,p_{n} $ $ (0<=p_{i}<=10^{9}) $ .
输出格式
Print an integer in a single line — the maximum possible value of sum.
输入输出样例
输入样例 #1
5 2 1
1 2 3 4 5
输出样例 #1
9
输入样例 #2
7 1 3
2 10 7 18 5 33 0
输出样例 #2
61