SRM 671 div1 easy:BearCries - mayoko’s diary

頭良すぎて禿げた。 med より難しくないですかこれ。

問題

解法

dp[i][single][pair] = i 番目の文字を見ている時点で, 「;」のようにセミコロンが単体でまだペアになる文字が決まっていないものが single 個あって, 「;_」や「;___」のようにセミコロンとアンダーバーがセットになったものが pair 個あるような場合の数
とします。すると, 答えは dp[n][0][0] となります。遷移については下のコードを参考に…

const int MAXN = 222;
const ll MOD = 1e9+7;
ll dp[MAXN][MAXN][MAXN];

void add(ll& a, ll b) {
    (a += b) %= MOD;
}

class BearCries {
public:
    int count(string message) {
        int n = message.size();
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;
        for (int i = 0; i < n; i++) for (int s = 0; s < n; s++) for (int p = 0; p < n; p++) {
            if (dp[i][s][p] == 0) continue;
            if (message[i] == ';') {
                // ; を増やす
                add(dp[i+1][s+1][p], dp[i][s][p]);
                // ;_ を使って顔完成
                if (p > 0) add(dp[i+1][s][p-1], p*dp[i][s][p]);
            } else {
                // ; を使って ;_ を作る
                if (s > 0) add(dp[i+1][s-1][p+1], s*dp[i][s][p]);
                // ;_ を使って _ を伸ばす
                if (p > 0) add(dp[i+1][s][p], p*dp[i][s][p]);
            }
        }
        return dp[n][0][0];
    }
};