题目名称	146. [USACO Jan08] 贝茜的晨练计划
输入输出	`cowrun.in/out`
难度等级	★★
时间限制	1000 ms (1 s)
内存限制	64 MiB
测试数据	10
题目来源	BYVoid 于2008-10-05加入
开放分组	全部用户
提交状态
分类标签	USACO 动态规划
	分享题解

通过：194，提交：520，通过率：37.31%
dateri	100	0.000 s	0.03 MiB	C++
leon	100	0.010 s	0.17 MiB	C++
TARDIS	100	0.014 s	0.15 MiB	C++
digital-T	100	0.030 s	0.43 MiB	C++
leon	100	0.032 s	0.43 MiB	C++
Hyoi_0Koto	100	0.032 s	0.43 MiB	C++
ztx	100	0.033 s	0.37 MiB	C++
svideo	100	0.033 s	0.43 MiB	C++
TARDIS	100	0.033 s	7.77 MiB	C++
face!shirk	100	0.037 s	0.43 MiB	C++

本题关联比赛
专项训练十题
20181004

关于贝茜的晨练计划的近10条评论(全部评论)
f[i][j]表示前i分钟在疲劳度为j的情况下所能走的最远distance f[i][0]=max(f[i-1][0],f[i-j][j]) i-j>=0; f[i][j]=max(f[i][j],f[i-1][j-1]+d[i]); ~ GROWL GOOD BOYส็ 2016-10-13 08:10 7楼
卡我三维数组QAQ 安呐一条小咸鱼。 2016-08-08 06:23 6楼
没看青题，居然是一直休息到体力为0..... digital-T 2014-06-09 14:29 5楼
没看青题，居然是一直休息到体力为0..... 考试时要是遇见这题估计会跪，因为做的DP还是太少了。。。。。。天下第一的吃货殿下 2012-10-29 20:29 4楼
吐个槽：每天进行N（N<=10000）分钟跑步，逆天啊，一天一共就24*60=1440分钟啊囧~ 天下第一的吃货殿下 2012-10-29 19:47 3楼
水了，瞬间交了5、6次才过 Truth.Cirno 2012-10-29 16:34 2楼
没看青题，居然是一直休息到体力为0..... feng 2012-10-19 16:59 1楼

146. [USACO Jan08] 贝茜的晨练计划

★★ 输入文件：cowrun.in 输出文件：cowrun.out 简单对比
时间限制：1 s 内存限制：64 MiB

【题目描述】

奶牛们打算通过锻炼来培养自己的运动细胞，作为其中的一员，贝茜选择的运动方式是每天进行N(1 <= N <= 10,000)分钟的晨跑。在每分钟的开始，贝茜会选择下一分钟是用来跑步还是休息。

贝茜的体力限制了她跑步的距离。更具体地，如果贝茜选择在第i分钟内跑步，她可以在这一分钟内跑D_i(1 <= D_i <= 1,000)米，并且她的疲劳度会增加1。不过，无论何时贝茜的疲劳度都不能超过M(1 <= M <= 500)。如果贝茜选择休息，那么她的疲劳度就会每分钟减少1，但她必须休息到疲劳度恢复到0为止。在疲劳度为0时休息的话，疲劳度不会再变动。晨跑开始时，贝茜的疲劳度为0。

还有，在N分钟的锻炼结束时，贝茜的疲劳度也必须恢复到0，否则她将没有足够的精力来对付这一整天中剩下的事情。

请你计算一下，贝茜最多能跑多少米。

【输入格式】

第1行: 2个用空格隔开的整数：N 和 M

第2..N+1行: 第i+1为1个整数：D_i

【输出格式】

第1行: 输出1个整数，表示在满足所有限制条件的情况下，贝茜能跑的最大距离

【输入样例】

【输出样例】

【样例解释】

贝茜在第1分钟内选择跑步（跑了5米），在第2分钟内休息，在第3分钟内跑步（跑了4米），剩余的时间都用来休息。因为在晨跑结束时贝茜的疲劳度必须为0，所以她不能在第5分钟内选择跑步。