Topcoder SRM671 Div1 Easy: BearCries
MedよりもEasyの方が難しいような
問題
";_;" や ";_______;" のような長さ1以上のアンダースコアを囲んだ顔文字を考える。渡された文字列を1つ以上の顔文字に分解したい。分解の仕方は何通りあるか答えよ。
解法
ここの解説と提出コードを参考に(というよりほとんど写経)しています。
DPで解いていく。dp[位置][余っている";"の個数][余っている";_..."の個数]=(分解の仕方の数)としてdp表を更新していけばO(N3)で解ける。
ll mod = 1000000007; ll dp[205][205][205]; class BearCries { public: void add(ll &a, ll b) { a += b; a %= mod; } int count(string message) { int n = message.size(); rep(i, 205) rep(j, 205) rep(k, 205) dp[i][j][k] = 0; dp[0][0][0] = 1; rep(i, n) rep(single, n) rep(ready, n) { if (dp[i][single][ready] == 0) continue; ll x = dp[i][single][ready]; if (message[i] == ';') //シングルの";"を1つ増やす add(dp[i + 1][single + 1][ready], x); //";_..."を1つ消費して顔文字を完成させる if (ready > 0) add(dp[i + 1][single][ready - 1], ready * x); } else { //";_.."から1つ選んで +"_" if (ready > 0) add(dp[i + 1][single][ready], ready * x); //シングルの";"の1つを";_"にする if (single > 0) add(dp[i + 1][single - 1][ready + 1], single * x); } } return dp[n][0][0]; } };
まとめ
このDPは今の自分じゃ書き下せないなあ