ZUFEOJ
Home
ProblemSet
Source/Category
Contest
Status
Ranklist
F.A.Qs
ContestProblemSetList
Login
Register
问题 N: 曙曙献爱心(DP)
内存限制:128 MB
时间限制:1 S
题面:传统
评测方式:文本比较
上传者:
提交:437
通过:243
返回比赛
提交
提交记录
题目描述
曙曙欢度国庆,来到五一大道发现人头攒动,这是因为大家都准备从五一广场上那个大屏幕观看新中国国庆阅兵式!这虽然是一件很喜庆的事情,可却让 CS 市的警察局长伤透了脑筋,因为人潮拥挤很容易发生安全事故。
为了防止意外以及能够及时处理安全问题。他们特意将五一大道上分成了 N 等份,每一份设置一个群众集会点,总共有 N 个集会点。在国庆这天每个聚集点都会聚集一定数量的群众,而同时也会有警察来管理这些集会点。因为 CS 其他很多地方都需要巡逻,所以只有有限的 M 个警察能够被分配到了五一大道上,而他们的能力也有限,一个人只能管理连续的 K 个集会点。热心的曙曙决定帮忙,在给出每个集会点将要聚集的群众人数,曙曙通过编程告诉警察最多能够管理到多少群众。
如有 10 个集会点,3 个警察,每个警察能管理连续 2 个集会点。
10 5 34 4 26 12 75 15 8 20
所以最多能够管理到 167 个群众。
输入格式
manage.in 第一行有三个数 N,M,K。如题所述。
接下来一行 N 个数,第 i 个数 A[i]表示五一大道上集会点 i 上的群众人数;
输出格式
manage.out 输出共一行一个数,表示警察最多能管理的群众人数。
输入样例
复制
7 4 1 2 43 32 4 64 1 10
输出样例
复制
149
数据范围与提示
【数据范围】
30%的数据: 1≤N,M,K≤100; 1≤A[i]≤20;
100%的数据: 1≤N,M,K≤1,000; 1≤A[i]≤200,000;
分类标签
动态规划
前缀和
(海曙区2017第4题)