RBS

题面

定义括号序列为只包括 $\texttt{(}$ 和 $\texttt{)}$ 的字符串。一个匹配的括号序列（简记为 RBS）满足，可以在其中加入 $1$ 和 $+$ ，将其转化为合法的代数式，例如：

• $\texttt{()()}$ 和 $\texttt{(())}$ 是匹配的
• $\texttt{)(}$ 和 $\texttt{(}$ 和 $\texttt{)}$ 不是。

将两个字符串拼接在一起简记为 $x+y$ 。例如， $\texttt{()()}+\texttt{)(}=\texttt{()())(}$ 。

给定 $n$ 个括号序列 $s_1\sim s_n$ ，你可以将他们任意重新排序，要求使得最终排序后的字符串满足 $s_1+\dots+s_n$ 的 RBS 前缀个数最多。

$1\le n\le 20$

题解

状压 $\mathcal{O}(n2^n)$ 。

代码

const int N = 25, M = 4e5 + 5, tN = 1048580;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {
	int n, ans;
	int ns[N], sc[N][M << 1], ss[N], sn[N];
	char s[M];
	int f[tN], sum[tN];
	int main () {
		n = Read();
		for (int i = 1; i <= n; i++) {
		   	scanf ("%s", s + 1); 
			ns[i] = strlen(s + 1);
			for (int j = 1; j <= ns[i]; j++) {
				ss[i] += (s[j] == '('? 1: -1);
				sn[i] = min(ss[i], sn[i]);
				if(sn[i] >= ss[i])sc[i][-ss[i]] ++;
			}
		}
		memset (f, -0x3f3f3f3f, sizeof f);
		f[0] = 0;
		for (int j = 0; j < (1 << n); j++) {
			for (int i = 1; i <= n; i++) {
				if ((j >> i - 1) & 1) continue;
				if (sum[j] + sn[i] < 0) {
					ans = max (ans, f[j] + sc[i][sum[j]]);
					sum[j | (1 << i - 1)] = sum[j] + ss[i];
				} else {
					f[j | (1 << i - 1)] = max(f[j | (1 << i - 1)], f[j] + sc[i][sum[j]]);
					sum[j | (1 << i - 1)] = sum[j] + ss[i];
				}
			}
			ans = max(ans, f[j]);
		}
		printf ("%d\n", ans);
		return 0;
	}
}

int main () {
	freopen("seq.in", "r", stdin);
	freopen("seq.out", "w", stdout);
	Main::main();
	return 0;
}