WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM671 Div1 Easy "BearCries"

解法

dpる。

dp[i][j][k] := i-1番目までの文字を考えた時に、
既にアンダーバーが付与しており、ペアが組まれていないセミコロンがj個あり
アンダーバーが付与しておらず、ペアが組まれていないセミコロンがk個あった時の場合の数
dp初期化

何も考えていないとき、ペアが組まれていないセミコロンの数は0なので、

dp[0][0][0] = 0;
dp更新

i番目の文字がセミコロンだった時、
右目として使う(既にアンダーバーが付与しており、ペアが組まれていないセミコロンとペアを組む)事にすると、

dp[i][j - 1][k] += dp[i][j][k] * j;

左目として使う事にすると

dp[i][j][k + 1] += dp[i][j][k];

i番目の文字がアンダーバーだった場合、
新たな口として使う(アンダーバーが付与していない、ペアが組まれていないセミコロンの口となる)事にすると、

dp[i][j + 1][k - 1] += dp[i][j][k] * k;

口を長くするために使う(アンダーバーが付与している、ペアが組まれていないセミコロンの口となる)事にすると、

dp[i][j][k] += dp[i][j][k] * j;
dp答え

n - 1までの文字を考えたときに、全てのセミコロンはペアを組まれている必要があるので、

dp[n][0][0]

ソースコード

const int MOD = 1000000007;
long long dp[202][202][202];

class BearCries {
    public:
    int count(string message) {
        int n = message.size();

        // dp初期化
        memset(dp, 0, sizeof(dp));
        dp[0][0][0] = 1;

        // dp更新
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    long long val = dp[i][j][k];
                    if (message[i] == ';') {
                        // 閉じよう
                        if (j > 0) {
                            add(dp[i + 1][j - 1][k], val * j);
                        }
                        // 開けよう
                        add(dp[i + 1][j][k + 1], val);
                    } else {
                        // 閉じれない奴につけよう
                        if (k > 0) {
                            add(dp[i + 1][j + 1][k - 1], val * k);
                        }
                        // 既に閉じれる奴につけよう
                        if (j > 0) {
                            add(dp[i + 1][j][k], val * j);
                        }
                    }
                }
            }
        }

        // 答え算出
        return dp[n][0][0];
    }

    void add(long long& tar, long long val) {
        tar += val;
        tar %= MOD;
    }
};