Skip to content

11134: 【原1134】主任补觉

题目

题目描述

author: Wen Xu 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1134

Description

勤奋的大学霸主任为了要写Scheme解释器,每天都奋斗到早上2点以后。他实在太累了,于是决定拿出一天好好补觉。

他把这一天等分成了n个时间段,在每个时间段睡觉能获得精神点数不尽相同,在第i段时间能获得V[i]的精神点数。由于勤奋的主任觉得整天都睡太堕落了,他决定最多只能花m个时间段睡觉。至于其他的时间吗...那自然是勤奋地码代码...

有两点事情要特别注意:

1.主任不可能一上床马上睡着,他在连续一段睡觉时间的第一个时间段不能获得此时的V。也就是说如果他在i...j中的所有时间都休息了,获得的精神点数为V[i+1]+...+V[j]。

2.所有的时间段呈环形分布,也就是说第n个时间段之后为第1个时间段。(有点畸形)

要求的自然是主任最多能获得的精神点数之和。

Input Format

第一行两个正整数n,m,分别代表时间段数量和主任准备选择的时间段数量。

接下来n行,每行一个非负整数V[i]。

Output Format

一行,表示yy最多能获得的精神点数之和

Sample Input

5 3
2
0
3
1
4

Sample Output

6

Limits

20% n<=20 50% n<=200 100% n<=5000,m<=n,V[i]<=10000

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!