SRM686 Div2 Hard "BracketSequenceDiv2"
解法
連続しない部分文字列の数え上げなので、基本的には以下のやり方で。
ekaing.hatenablog.com
あとは、最終的に全ての左カッコに右カッコのペアが出来ていなければならないので、超過した左カッコの数を記録しておく。
事後
難しいなぁ・・・
ソースコード
const long long MOD = 1000000007LL; long long dp[110][110]; class BracketSequenceDiv2 { public: int count(string s) { s += "D"; // ダミー int n = s.size(); // dp初期化 memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; i++) { if (s[i] == '(') dp[i][1] = 1; } // dp更新 int open_pre_pos = -1; // iから見て左側最寄りの'('の位置 int close_pre_pos = -1; // iから見て左側最寄りの')'の位置 for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { int m = j; if (s[i] == '(') m--; if (s[i] == ')') m++; if (m < 0 || n < m) continue; // open if (open_pre_pos != -1) { dp[i][j] += dp[open_pre_pos][m]; dp[i][j] %= MOD; } // close if (close_pre_pos != -1) { dp[i][j] += dp[close_pre_pos][m]; dp[i][j] %= MOD; } } if (s[i] == '(') open_pre_pos = i; if (s[i] == ')') close_pre_pos = i; } return dp[n - 1][0]; } };