求最少添加的括号数量非常简单,遍历一遍所有括号,记录一下失配的左括号和右括号的数量即为最少需要添加的括号数量。
重点是如何求出最后合法的方案数。
step 1
首先,将一个括号序列补充到合法的最小方案一定在原括号序列中存在一个分界点,在这个分界点左边,我们只需要添加左括号 (
,在这个分界点右边我们只需要添加右括号 )
,即左括号一定添加在右括号前边。
举个例子,对于序列 )(((()
,我们可以发现左括号确实是添加在右括号前面的。
所以我们就可以将序列分解为两部分,一部分只需要填左括号,一部分只需要填右括号,他们是相互独立的,所以我们可以求出填左括号的方案数,与填右括号的方案数相乘从而得到最终结果。
比如上边那个序列,我们可以分成 )
和 (((()
,然后分别填上左括号和右括号。
然后我们发现,如果将填右括号的序列完全反过来,那就又变成只需要填左括号的情况了,所以我们对于一个序列,只需要求出需要填多少个左括号即可。
(((()
反过来是 ())))
step 2
我们考虑如何求出在只需要填左括号的情况下的方案数量。
我们用一个数组 $v$ 来表示一个括号序列,其中:
$v_i$ 的值为第 $i$ 个右括号 )
与第 $i - 1$ 个右括号 )
之间的左括号个数(这里假设第 $0$ 个右括号的位置为 $0$)。
我们可以发现 $v$ 数组和括号序列是一一对应的,并且数组的大小应该是这个括号序列中右括号的个数。
例如 )(((()()
的 $v$ 数组应该是:$\{0, 4, 1\}$。
这样一来,我们可以发现一个数组是一个合法的括号序列的充要条件是对于任意的位置 $p$,满足:
$$ \sum_{i = 1}^pv[i] >= i $$
即对于任何一个位置,左括号数减掉右括号数要非负。
然后我们最终的合法序列还要能通过原序列通过增加左括号的方式得到,即原序列必须是合法序列的子序列。
我们假设最终的合法序列数组为 $v’$,原序列数组为 $v$,由于只添加左括号,所以这两个数组的大小应该相同,那么可以发现, $v$ 是 $v’$ 的子序列的充要条件是,对于任意的位置 $p$,满足:
$$ v’[p] >= v[p] $$
即最终序列的第 $p$ 个右括号与第 $p - 1$ 个右括号之间间隔的左括号数应不小于原序列的。
所以我们最终只需要求出满足上边两个条件的数组 $v’$ 的数量。
step 3
我们考虑通过动态规划的方式求解。
我们可以设 $f[i][j]$ 当前进行到数组 $v’$ 的第 $i$ 个位置,放的所有位置的数的总和为 $j$ 的方案数,我们可以得到如下转移方程($vn$ 为数组 $v$ 的大小):
$$ f[i][j] = \sum_{k = v[i]}^{vn} f[i - 1][j]$$
起始状态:
· $f[0][0] = 1$。
· 当 $j < \max(v[i], i + 1)$ 时,$f[i][j] = 0$。
这个 dp 可以用前缀和优化到 $O(n^2)$。
然后求出分界点位置分别 dp 求解即可,最终复杂度 $O(n^2)$。
code
#include <bits/stdc++.h>
#define mp(x, y) std::make_pair(x, y)
#define pb push_back
#define FOR(x, l, r) for(int x = l; x <= r; x++)
#define DO(x, r, l) for(int x = r; x >= l; x--)
#define vi std::vector
#define ALL(x) x.begin(), x.end()
const int MAXN = 1e3 + 4;
const int MOD = 1e9 + 7;
typedef long long ll;
typedef std::pair<int, int> Pair;
typedef std::pair<ll, int> Pairli;
const ll oo = 0x3f3f3f3f3f3f3f3f;
char str[MAXN], str2[MAXN];
int sum[MAXN], len, n;
int f[MAXN][MAXN], s[MAXN][MAXN];
int get(char *str, int n) {
vi<int> v;
int sn = 0;
FOR(i, 1, n) {
if(str[i] == '(') sn++;
else v.pb(sn), sn = 0;
}
int vn = v.size();
memset(f, 0, sizeof(f));
memset(s, 0, sizeof(s));
f[0][0] = 1;
FOR(i, 0, vn) s[0][i] = 1;
FOR(i, 0, vn - 1) {
FOR(j, std::max(v[i], i + 1), vn) {
f[i + 1][j] = (f[i + 1][j] + s[i][j - v[i]] - (j - vn - 1 >= 0 ? s[i][j - vn - 1] : 0)) % MOD;
s[i + 1][j] = (s[i + 1][j - 1] + f[i + 1][j]) % MOD;
}
}
if(f[vn][vn] < 0) f[vn][vn] += MOD;
return f[vn][vn];
}
void solve() {
int ans = 1;
scanf("%s", str + 1);
n = strlen(str + 1);
FOR(i, 1, n) {
if(str[i] == '(') sum[i] = sum[i - 1] + 1;
else {
sum[i] = sum[i - 1] - 1;
if(sum[i] < 0) sum[i]++, len++;
}
}
len += sum[n];
int cnt = 0;
DO(i, n, 1) {
if(sum[i] == 0) break;
str2[++cnt] = (str[i] == '(' ? ')' : '(');
}
ans = get(str, n - cnt);
ans = 1LL * ans * get(str2, cnt) % MOD;
printf("%d %d\n", len, ans);
}
int main() {
int T = 1;
// scanf("%d", &T);
while(T--) solve();
return 0;
}