1290: 奶牛的锻炼

参考代码:

#include<bits/stdc++.h>
using namespace std;
int dp[10005][1000];
int a[10005];
int n,m;
int dfs(int i,int j)
{
	if(i>n)return 0;//越界
	if(i+j>=n)return 0;//保证奶牛在终点疲惫度为0
	if(i==n)
	{
		return a[i];
	}
	if(dp[i][j]!=0)
	{
		return dp[i][j];
	}
	if(j==m)//疲惫值为m必须休息
	{
		return dp[i][j]=max(dp[i][j],dfs(i+j,0));
	}
	else if(j==0)//疲惫值为0时可选择休息或者跑步
	{
		return dp[i][j]=max(dfs(i+1,j+1)+a[i],dfs(i+1,0));
	}
	else//其他时候可以选择继续跑或者休息
	{
		return dp[i][j]=max(dfs(i+1,j+1)+a[i],dfs(i+j,0));
	}
	
}
int main()
{
	
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	dfs(1,0);
	cout<<dp[1][0];
	return 0;
}