题目描述

奶牛们打算通过锻炼来培养自己的运动细胞，作为其中的一员，贝茜选择的运动方式是 每天进行 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 个整数，表示在满足所有限制条件的情况下，贝茜能跑的最大距离

【输入样例】  5 2 5 3 4 2 10

【输出样例】  9

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

题解：

一、阶段划分

        在每一个时间点都要考虑疲劳值，跑步距离的变化，所以以时间点划分阶段

        此时满足最优子结构和无后效性

二、状态表达

        由于根据时间划分阶段，所以状态的第一维为时间；

        若以f[i]表示前i分钟所跑的最大距离，则无法体现疲劳值的变化，所以再开一维表示此时的疲劳值；

        即f[i][j]表示前i分钟，疲劳值为j时所跑的最大距离（f[i][j]数组为int类型）；

三、初始状态

        初始时时间为0，疲劳值为0，跑步距离为0；

        所以初值为f[0][0]=0;

四、状态转移方程

        1.上一时间休息到0，这一时间继续休息。则时间+1，疲劳值仍为0，距离不变

 f[i][0]=f[i-1][0];

        （此时与j的枚举无关，在第一层循环中赋值）

        2.前面某一时间停下休息，休息到现在疲劳值为0。则通过枚举停下来的时间更新此时跑步距离的最大值；

f[i][0]=max(f[i][0],f[i-j][j]);

        3.持续跑步。同样不断更新，在这一时间不同疲劳值的情况下所跑的最大距离

 f[i][j]=max(f[i][j],f[i-1][j-1]+c[i])

五、最终答案

        因最后时间的疲劳值为0，且要得到最后时间的跑步最大距离，则最终答案为f[n][0]

六、总结

        关注题中所有核心属性，依据划分阶段及每一阶段属性的变化、确定状态的维数等；

七、核心DP代码实现

void c_dp()
{
	f[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		f[i][0]=f[i-1][0];
		for(int j=1;j<=m;j++)
		{
			if(j<=i)
				f[i][0]=max(f[i][0],f[i-j][j]);
			f[i][j]=max(f[i-1][j-1]+cow[i],f[i][j]);
		}	
	}	
} 

八、本题代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int cow[11000];
int f[11000][510];
void c_dp()
{
	f[0][0]=0;
	for(int i=1;i<=n;i++)
	{
		f[i][0]=f[i-1][0];
		for(int j=1;j<=m;j++)
		{
			if(j<=i)
				f[i][0]=max(f[i][0],f[i-j][j]);
			f[i][j]=max(f[i-1][j-1]+cow[i],f[i][j]);
		}	
	}	
} 
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		cin>>cow[i];
	c_dp();
	cout<<f[n][0];
}