经典状压DP
首先如果所有的S中的左括号和右括号数量不一样,无论如果都无法拼成一个合法括号序列。然后开始状压DP,我们令dp[mask]表示为掩码mask为1的字符串已经被选取的方案数,那么答案就是dp[(1 << n) - 1]。
那么转移也很显然,对于一个v在当前mask中没有被选取,同时这个字符串可以接在当前mask后面那么就可以转移为dp[mask | (1 << v)] += dp[mask]
现在我们考虑什么是合法的转移。
对于一个合法括号序列,首先每一位上前缀的“(” 不少于 “)” 的数量,同时总共的( 和 ) 数量相等即可
那么我们对于每个字符串可以用一个数字记录 ( 的数量 减去 )的数量,这个这个数字>=0 那么就是合法的,这个数字后文用cnt表示。
如果你认为转移的时候,只要当前mask里的cnt + 不在mask 里的 v 的cnt >=0 那就错了,一个简单的反例就是 比如前缀是 ((()) 后面不能接 )))(((( ,虽然前面的cnt > 0 后面的 cnt > 0 但是显然 ((()))))((((是不合法的。
那么怎么解决呢
我们只需要记录前缀中cnt最小值就行了,只要mask的cnt + 接上的字符串的 cnt前缀最小值 >= 0,显然可以拼接,不难看出这个条件是可以拼接的等价条件。
时间复杂度O(n*2^n)
(打的时候猪逼了一开始写了个n方2^n的😭)
贴上AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
constexpr int MOD = 1e9 + 7, INF = 1e18;
void solve()
{
int n;
cin >> n;
int cnt = 0;
vector<int> a(n);//每个字符串( - )的数量差
vector<int> b(n, INF);// 每个数量差的最小值
for (int i = 0; i < n; i++)
{
string s;
cin >> s;
int sum = 0;
for (auto c: s)
{
if (c == '(') sum++;
else sum--;
b[i] = min(b[i], sum);
}
a[i] = sum;
cnt += sum;
}
if (cnt != 0)
{
cout << "0\n";//判掉不合法
return;
}
const int FULL = 1ll << n;
vector dp(FULL, 0);
dp[0] = 1;
for (int mask = 0; mask < FULL; mask++)
{
if (!dp[mask]) continue;
int sum = 0;//当前的差值
for (int u = 0; u < n; u++)
{
if (mask >> u & 1) sum += a[u];
}
for (int v = 0; v < n; v++)
{
if (mask >> v & 1) continue;
if (b[v] + sum < 0) continue;// 不合法转移判掉
dp[mask | (1ll << v)] = (dp[mask | (1ll << v)] + dp[mask]) % MOD;
}
}
cout << dp[FULL - 1] << '\n';
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int __ = 1;
cin >> __;
while (__--)
{
solve();
}
return 0;
}