7月17日备战Noip2017暑假集训2(A) 贝茜的晨练计划【动态规划】

晨练

【问题描述】

小 Y 打算通过锻炼来培养自己的运动细胞,他选择的运动方式是每天进行N分钟的晨跑(1<=N<=10000)。

在每分钟的开始,小 Y 会选择下一分钟是用来跑步还是休息。小 Y 的体力限制了他跑步的距离。更具体地,如果小 Y 选择在第 i 分钟内跑步,他可以在这一分钟内跑 D_i(1<=D_i<=1000)米,并且他的疲劳度会增加1。不过,无论何时小 Y 的疲劳度都不能超过 M(1 <=M<=500)。如果小 Y 选择休息,那么他的疲劳度就会每分钟减少 1,但他必须休息到疲劳度恢复到0为止。在疲劳度为 0 时休息的话,疲劳度不会再变动。晨跑开始时,小 Y 的疲劳度为 0。还有,在N分钟的锻炼结束时,小 Y 的疲劳度也必须恢复到0,否则他将没有足够的精力来对付这一整天中剩下的事情。

请你计算一下,小 Y 最多能跑多少米。

【输入格式】

第1行:2个用空格隔开的整数:n,m。

第2..n+1行:第i+1行为1个整数D_i。

【输出格式】

输出一行为一个整数,表示在满足所有限制条件的情况下,小y能跑的最大距离。

【输入样例】

5 2

5

3

4

2

10

【输出样例】

9

数据范围与约定

对于30%的数据:n<=50。

对于100%的数据:n<=10000。

继续阅读“7月17日备战Noip2017暑假集训2(A) 贝茜的晨练计划【动态规划】”