SRM671 div.1 300 BearCries
解法
配るDP。dp[i][s][p] = (i番目まで見て、s個';'がペアになっていなくて、p個';'と'_*'がペアになっているときの場合の数)とする。
このとき、dp[0][0][0]=1として、N=len(message)とすると、dp[i][s][p]を(i:0->N, s:0->N, p:0->N)で以下のように更新していく。
- message[i] = ';'のとき
- dp[i+1][s+1][p] += dp[i][s][p]
- dp[i+1][s][p-1] += p * dp[i][s][p] (p > 0) (ペアになっているp個のうちどれかとmessage[i]がペアになり、泣き顔が完成する)
- message[i] = '_'のとき
- dp[i+1][s][p] += p * dp[i][s][p] (ペアになっているp個のうちどれかとmessage[i]がペアになり、口が伸びる)
- dp[i+1][s-1][p+1] += s * dp[i+1][s][p] (s > 0) (ペアになっていないs個のうちどれかとmessage[i]がペアになり、ペアが1増える)
答えはdp[N][0][0]である。
計算量
O(N^3)
コード
感想
- ペアを作るときにdp[i][ペアを作ってない][ペアを作った]という形でのdpを考えるというのは応用がききそう
- バランスを取らないといけないときに、バランスを考慮せずに探索して最後にバランスが取れている部分だけ答える、というのはわりとよく見かける手法だと思う。
