CodeForces #267_Div2 : C. George and Job
問題
大きさnの整数配列pが与えられる。
この配列の内、重複しない大きさmの区間をk個選択した時の合計値を最大化させたい。
解法
動的計画法
dp[ i ][ j ] := j番目のindexに位置し、i個の区間を選択済時の最大値
例えば、j番目のindexから始まる区間を選択する場合は以下のように更新を行う。
dp[ i+1 ][ j + m ] = max(dp[i + 1][j + m -1], dp[i][j] + (jからj+m-1までの和))
和の計算は事前に累積和を求めておくことでで得られるため、
全体の計算量はとなる。
Javaで空間計算量がとなるとギリギリMLEとなってしまうので、
配列の再利用ができるように、k → nの順でループを回し空間計算量をで抑える。
