3361 Running

問題概要

牛がN分間の間次のようなマラソンをする。


1分間ごとに走るか休むかを選べ、走る場合にはi分目にはd[i]の距離を走れて、疲労度が1増える。
休む場合1分間に疲労度が1回復するが、0になるまで再び走ることができない。
疲労度はMを超えてはならない。


N分間の間に走れる最大の距離を求めよ。
ただし、マラソンを終えた後の疲労度は0になっていなければならないものとする。


N≦10000,M≦500を満たす。

解法

dp[i][j]に、i分経った時点で疲労度がjの時に進める最大の距離をもって表を更新していくdpをすればよい。

ソースコード

int n,m,d[10001];
int dp[10001][501];

int main()
{
	scanf("%d%d",&n,&m);
	rep(i,n)scanf("%d",d+i);
	rep(i,n)rep(j,m+1)
	{
		if(j<m)dp[i+1][j+1]=max(dp[i+1][j+1],dp[i][j]+d[i]);
		if(i+j<=n)dp[i+max(j,1)][0]=max(dp[i+max(j,1)][0],dp[i][j]);
	}
	printf("%d\n",dp[n][0]);
	return 0;
}