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