P83908

电脑班的裁员

难度 5 级 动态规划入门 线性
讨论 统计 3通过 3提交 100%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

隔壁的新初一电脑班刚考过一场试,又到了BlingBling的裁员时间,老师把这项工作交给了ZZY来进行。而ZZY最近忙着刷题,就把这重要的任务交(tui)给了你。

ZZY有独特的裁员技巧:每个同学都有一个考试得分ai(-1000<=ai<=1000),在n个同学(n<=500)中选出不大于k段(k<=n)相邻的同学留下,裁掉未被选中的同学,使剩下同学的得分和最大。要特别注意的是,这次考试答错要扣分【不要问我为什么】,所以得分有可能为负。

输入

第一行为n,k,第二行为第1~n位同学的得分。

输出

一个数s,为最大得分和。

样例

样例 1
输入
5 3
1 -1 1 -1 1
输出
3

来源

luogu

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交