Educational Codeforces Round 115 F. RBS の解法です． 解説ACです．
問題概要
文字 ( と ) のみからなる空でない文字列全体の集合を $S$ とする．
$s \in S$ に対し，$s$ の空でない prefix であって，
括弧の対応が取れているものの数を $f(s)$ と書くことにする．
例えば $f(\verb!"()()()))"!) = 3$,
$f(\verb!"(()())(("!) = 1$．
$S$ の要素が $n$ 個与えられる． これらを並べ替えて連結して得られる文字列 $s$ について，$f(s)$ の 最大値を求めよ．
制約: $ 1 \leq n \leq 20$，与えられる文字列の長さの和は $4\times 10^5$ 以下． 制限時間3秒．
解法
0-index で記述する． $\bar{n} := \{0, \ldots, n-1\}$ とする．
$s \in S$ に対し，現れる ( の数から ) の数を引いたものを $g(s)$ と書く．
$s \in S$ で，全ての $i < |s|$ に対して $g(s) \geq 0$ であるものの集合を
$L$ と書く．$D := S \setminus L$．
$x \subseteq \bar{n}$ に対し， $\{ s_i \mid i \in x \}$ を並び替えて連結して得られる文字列 の集合を $P(x)$ と書く． $P(x)$ の要素 $s$ について，$g(s)$ の値は全て等しい．この値を $b(x)$ と書く． $\newcommand{\live}{\text{live}}\newcommand{\dead}{\text{dead}}$
- $\live[ x ] := \max \{ f(s) \mid s \in P(x) \cap L \}$
- $\dead[ x ] := \max \{ f(s) \mid s \in P(x) \cap D \}$
ただし，$\max \varnothing = -\infty$．
すると，求める値は $\max( \text{live}[\bar{n}], \text{dead}[\bar{n}] )$ である．
これをDPで求める．初期化:
- $\live[ \varnothing ] = 0$
- $\dead[ \varnothing ] = -\infty$
遷移は次のようになる．
- $\text{updMax}(\dead[ x \cup \{k\} ], \dead[ x ])$
- $b(x) + g(s_k) < 0$ のとき， $\text{updMax}(\dead[x \cup \{k\} ], \live[ x ] + h(s_k, b(x)))$
- $b(x) + g(s_k) \geq 0$ のとき， $\text{updMax}(\live[x \cup \{k\} ], \live[ x ] + h(s_k, b(x)))$
ここで，$h(s, b)$ は，$s$ において $g(i) = -b$ かつ すべての $j < i$ に対して $g(j) \geq -b$ であるような $i$ の数であり， これらは前計算で求めておくことができる．
計算量は $O(n2^n)$