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; }