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