给\(n\)个括号序列,可以对这些序列任意排列,然后连接成一整个括号序列。求一个排列,使得连接成的括号序列的真前缀是合法括号序列的个数最多。\(n\le 20\)
观察性质,发现括号序列的balance一旦小于0,后面无论是什么都不会使得当前前缀的合法。合法括号序列的前缀的个数即balance为0且前面balance都大于等于0的个数。
显然看到\(n\)那么小,就想到枚举串。设\(f(i,j)\)为选择\(i\)的字符串集合(状压)作为前缀,\(j\)代表这个前缀是否合法,的最多的个数。每次枚举在前缀后面添加什么字符串,会对答案产生贡献。由于知道\(i\)的字符串集合,就知道当前前缀结尾的balance。预处理出添加字符串,前面的balance的多少时对答案的贡献即可。然后转移就很容易。预处理用一个指针移动O(n)即可处理出来。
#include <bits/stdc++.h> #define endl '\n' #define IOS std::ios::sync_with_stdio(0); cin.tie(0); cout.tie(0) #define mp make_pair #define seteps(N) fixed << setprecision(N) typedef long long ll; using namespace std; /*-----------------------------------------------------------------*/ ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} #define INF 0x3f3f3f3f const int N = 2e6 + 10; const double eps = 1e-5; bool fg[30][N]; int val[30][N]; int dp[N][2]; bool ok[N]; vector<vector<int>> bal; int calbal(int m) { int res = 0; int cur = 0; while(m) { if(m & 1) res += bal[cur].back(); cur++; m >>= 1; } return res; } int main() { IOS; int n; cin >> n; int tot = 0; for(int i = 1; i <= n; i++) { string t; cin >> t; vector<int> bt(t.size()); tot += t.size(); for(int j = 0; j < bt.size(); j++) { bt[j] = (t[j] == '(') ? 1 : -1; if(j > 0) bt[j] += bt[j - 1]; } bal.push_back(bt); } for(int i = 0; i < n; i++) { vector<int> &tar = bal[i]; int mi = tar.front(); for(int j = 0; j < tar.size(); j++) { mi = min(mi, tar[j]); } int p = 0; for(int j = 0; j <= tot; j++) { if(mi + j < 0) fg[i][j] = 1; else fg[i][j] = 0; int cnt = 0; while(p < tar.size() && -tar[p] <= j) { if(-tar[p] == j) cnt++; p++; } val[i][j] = cnt; } } ok[0] = 1; for(int i = 1; i < (1 << n); i++) { int vb = calbal(i); for(int j = 0; (1 << j) <= i; j++) { if(i & (1 << j)) { int bit = i ^ (1 << j); int cb = vb - bal[j].back(); dp[i][1] = max(dp[i][1], dp[bit][1]); if(ok[bit] && cb >= 0) { int flag = fg[j][cb]; dp[i][flag] = max(dp[i][flag], dp[bit][0] + val[j][cb]); ok[i] |= !flag; } } } } int ans = dp[(1 << n) - 1][1]; if(ok[(1 << n) - 1]) ans = max(ans, dp[(1 << n) - 1][0]); cout << ans << endl; }