SRM 670 div1 easy:Bracket107
寝坊したので SRM 670 は不参加でした。
解法
実は条件を満たすような LCS の最大値は文字列 s の長さを n として必ず n-1 であることがわかります。これは, 以下の場合分けを考えることによりわかります。
s が (())()()のように2つ以上の Correct Bracket の場合は s は A(B) という形になります。この時は, 文字列として (AB) という文字列を作れば LCS の大きさは n-1 になります。
s が 1 つにまとまった Correct Bracket の場合は s は (A) という形になります。この時は, 文字列として A() という文字列を作れば LCS の大きさは n-1 になります。
ということで, LCS の大きさの最大値は n-1 です。なので, 元の文字列から 1 文字抜き取った文字列に '(' か ')' を挿入して, それが Correct Bracket になるなら答えに加算していく, ということをやれば OK です。
bool check(string s) { stack<char> st; for (char c : s) { if (c == '(') st.push(c); else { if (st.empty()) return false; st.pop(); } } return st.empty(); } class Bracket107 { public: int yetanother(string s) { set<string> S; int n = s.size(); for (int i = 0; i < n; i++) { string t; for (int j = 0; j < n; j++) { if (j == i) continue; t += s[j]; } if (check("("+t)) S.insert("("+t); for (int j = 0; j < n-1; j++) { for (int f = 0; f < 2; f++) { string nt; for (int k = 0; k <= j; k++) { nt += t[k]; } if (f == 0) nt += "("; else nt += ")"; for (int k = j+1; k < n-1; k++) nt += t[k]; if (check(nt)) S.insert(nt); } } } return S.size()-1; } };