SRM592 Div1 Easy - LittleElephantAndBalls
問題
ボールをn個持っており、ボールiの色は左から順にs[i]である(s[i]は'R' か 'G' か 'B')
これを左から順に空のテーブルに一列に置いていく
ボールiを置くとき、
ボールの列の端に置く場合) 元のボールの列に含まれるボールの色の種類数をスコアに加える
ボールの列の隙間に置く場合) その隙間の左右それぞれの列に含まれるボールの色の種類数の和をスコアに加える
最終的に得られるスコアの最大値を求めよ
1 <= n <= 50
解法
ちょっと考えると、毎回
テーブルのボールの列の長さが偶数のとき) 列の真ん中
そうでないとき) 列の左半分と右半分で今加えようとしてるボールの色が含まれない方があればそっち側の一番真ん中に近い隙間、そうでなければどっちでもいい
にボールを置き続けるのが最善であることがわかる
今列にある各色のボールを最大2個まで数えておいて、それらの和を答えに足していけばいい
class LittleElephantAndBalls { public: int getNumber(string s) { int res = 0, a[3] = {}; each(i,s) { res += accumulate(a,a+3,0); if (i=='R') a[0] = min(2, a[0]+1); else if (i=='G') a[1] = min(2, a[1]+1); else a[2] = min(2, a[2]+1); } return res; } };