問題概要
長さnの数列aがある.
aのあるk番目を取り除くとき, a[k]-1, a[k]+1の値を取る場所も全て取り除く.
このとき得点a[k]を得る.
これを繰り返すとき, 得られる得点の総和の最大はいくらになるか.
解法
まず各値は数列中に何個含まれるかしらべる.
そうするとある値a[k]を取ったとき, a[k]-1とa[k]+1が消えることから他のa[k]は全て取れる.
また前を決めれば後ろも決められるのは明らかなので, 小さい数から順に見ていき
dp[k+1][0] := k番目を取らないときの最大
dp[k+1][1] := k番目を取るときの最大
とDPすればよい.
コード
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
|