SRM 686 div1 easy: BracketSequenceDiv1
解法
制約からして半分全列挙だろと思い dp は考えませんでした(あとで dp 解書きます)。
前半部分で例えば " ( ( ) ( [ ] [ (" という文字列を取り出したら, 対応する括弧を取り除いて " ( ( [ ( " にします(" ( ] [ " の様に対応的にありえないものがあったらそれは無視する)。
で, 後半部分で対応する括弧を取り除いた後に " ) ] ) ) " となるものがあったら, 前計算していた " ( ( [ ( " の数だけ答えに加算する, という感じです。今回は空文字が許されていないので最後に答えから 1 を引きます。
下のコードでは map
class BracketSequenceDiv1 { public: long long count(string s) { cout << "test" << endl; int n = s.size(); int n1 = n/2, n2 = n-n1; map<string, int> m1; for (int i = 0; i < 1<<n1; i++) { string t; for (int j = 0; j < n1; j++) { if ((i>>j)&1) t += s[j]; } bool ng = false; stack<char> st; for (char c : t) { switch (c) { case '(': st.push(c); break; case '[': st.push(c); break; case ')': if (st.empty() || st.top() != '(') { ng = true; } else { st.pop(); } break; case ']': if (st.empty() || st.top() != '[') { ng = true; } else { st.pop(); } break; } } if (ng) continue; string u; while (!st.empty()) { u += st.top(); st.pop(); } reverse(u.begin(), u.end()); m1[u]++; } ll ans = 0; for (int i = 0; i < 1<<n2; i++) { string t, tar; for (int j = n-1; j >= n1; j--) { if ((i>>(j-n1))&1) t += s[j]; } stack<char> st; bool ng = false; for (char c : t) { switch(c) { case ')': st.push(c); break; case '(': if (st.empty() || st.top() != ')') { ng = true; } else { st.pop(); break; } break; case ']': st.push(c); break; case '[': if (st.empty() || st.top() != ']') { ng = true; } else { st.pop(); break; } break; } } if (ng) continue; string u; while (!st.empty()) { u += st.top(); st.pop(); } reverse(u.begin(), u.end()); for (char & c : u) { if (c == ')') c = '('; else if (c == ']') c = '['; } ans += m1[u]; } return ans-1; } };