TopCoder SRM 592 Div1 Easy LittleElephantAndBalls

問題

R, G, Bどれかの色をしたボールがn個あり、i個目の色はS[i]である。
このボールをテーブルの上に1番目から順に一列に並べていく。


i番目のボールを置くとき、これまで並べたボールの両端または好きな隙間に入れることができる。
新しいボールの左側にあるボールの色の種類をa,
右側にあるボールの色の種類をbとすると、a + bの得点が入る。(毎回)


得られる得点の最大値を求めよ。

制約条件

n≦50
S[i]はR, G, Bのどれか

方針

全部を中央に挿入していく、みたいな感じで考える。
置くべき場所の左側にR, G, Bがあるか、右側にR, G, Bがあるかをビットとして持つようなビットDPをすれば、全部の場合を尽くすことができる。


ボールを置いたあと、それが左右のどちらに属するかを決めてやる。
実は貪欲でいいらしい。

ソースコード

int dp[51][1 << 6];

class LittleElephantAndBalls {
	public:
	int getNumber(string S) {
		memset(dp, -1, sizeof(dp));
		
		dp[0][0] = 0;
		rep(i, S.size()) rep(j, 1 << 6) if(dp[i][j] >= 0){
			
			int nxt = dp[i][j] + __builtin_popcount(j >> 3) + __builtin_popcount(j & 7);
			int col = S[i] == 'R' ? 0 : S[i] == 'G' ? 1 : 2;
			
			dp[i + 1][j | 1 << col + 3] = max(dp[i + 1][j | 1 << col + 3], nxt);
			dp[i + 1][j | 1 << col + 0] = max(dp[i + 1][j | 1 << col + 0], nxt);
		}
		int ans = 0;
		rep(i, 1 << 6) ans = max(ans, dp[S.size()][i]);
		return ans;
	}
};