【2021年省赛B组】试题J: 括号序列

题解

step 1

我们将左括号的值看作1， 左括号的值看作-1。 定义$sum[i]$表示前$i$个括号的和， $n$表示序列的长度， 那么对于一个合法序列，其必定满足$\forall i \in (1, n), sum[i] \geqslant 0$且$sum[n] = 0$。

step 2

我们需要将添加括号使用原括号序列成为合法括号序列。 题目要尽可能少的添加括号，所以我们添加的左括号必然只能和原序列中的右括号匹配；我们添加的右括号必然只能和原序列中的左括号匹配。若我们添加的左括号和我们添加的右括号匹配了，那么它们无疑是一对没有意义的添加。 于是添加的左括号的方案只和原序列中的右括号相关，添加的右括号的方案只和原序列中的左括号相关，所以左右括号的添加是相互独立的。设左括号的添加方案为$f1$, 右括号的添加方案为$f2$， 那么显然最后的答案就是$f1 \times f2$。

step 3

60pts

我们先考虑左括号的添加方案数。 设原序列中有$cnt$个右括号， 我们以原序列中的右括号为分界点， 那么一共可以划分出$cnt+1$个区域。我们只能在第$1$~$cnt$个区域添加左括号，因为若是在第$cnt + 1$​​区域添加左括号， 将不会有右括号可以与它匹配。

定义$dp[i][j]$表示前$i$个区域（右括号）， 在我们添加了若干个左括号后，添加了左括号一共有$j$个左括号的方案数。对于两个不同的方案，它们至少有一个区域添加的左括号的个数不相同，于是可得：

$$dp[i][j] = dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2] + \cdots + dp[i - 1][j] $$

注意：

由于我们要的是合法序列，所以当右括号的个数为$i$时，它前面的左括号的个数必然大于等于$i$。我们定义$sum[i]$表示第$i$个右括号之前的左括号个数， 当$i > sum[i]$时， $j$必须满足$j \geqslant i - sum[i]$。

for(int i  = 2; i <= n; i++)
{
    for(int j = max(0ll, i - sum[i]); j <= cnt; j++)
    {
        for(int k = 0; k <= j; k++)
        {
            dp[i][j] += dp[i - 1][k];
            dp[i][j] %= mod;
        }
    }
}

于是添加左括号的方案数就计算完成了。对于右括号的添加方案，我们可以将原括号序列反转，并令( -> ), (->)，然后按照求左括号的方案数的方法再求一遍即可。

提交代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e3 + 10, mod = 1e9 + 7;
string s;
int dp[N][N], sum[N];

int calc(int cnt, bool flag)
{
	if(!cnt) return 1;
	memset(dp, 0, sizeof dp);
	memset(sum, 0, sizeof sum);
	memset(pre, 0, sizeof pre);
	
	if(!flag)
	{
		reverse(s.begin(), s.end());
		for(int i = 0; i < s.size(); i++)
		{
			if(s[i] == ')') s[i] = '(';
			else s[i] = ')';
		}
	}
	
	int n = 0, now = 0;
	for(int i = 0; i < s.size(); i++)
	{
		if(s[i] == ')') sum[++n] = now;
		if(s[i] == '(') now++;
	}
	
	if(sum[1] > 0) dp[1][0] = 1;
	for(int i = 1; i <= cnt; i++) dp[1][i] = 1;
	
	for(int i  = 2; i <= n; i++)
	{
		for(int j = max(0ll, i - sum[i]); j <= cnt; j++)
		{
			for(int k = 0; k <= j; k++)
			{
				dp[i][j] += dp[i - 1][k];
				dp[i][j] %= mod;
			}
		}
	}
	return dp[n][cnt];
}
void solve()
{
	cin >> s;
	int tot  = 0, cnt1 = 0, cnt2 = 0;
	for(auto x : s)
	{
		if(x == '(') tot++;
		else tot--;
		
		if(tot < 0) cnt1++, tot = 0;
	}
	cnt2 = tot;
	cout << calc(cnt1, 1) * calc(cnt2, 0) % mod << "\n";
}
signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int t = 1;
	while(t--) solve();
	return 0;
}

100pts

上述$O(n^3)$做法怎么优化呢？

其实很简单，如果你做过完全背包，那么应该一眼就能想到使用前缀和来优化。

对于$dp[i-1][0] + dp[i - 1][1] + dp[i - 1][2] + \cdots + dp[i - 1][j]$，我们可以用其他的式子来代替。

即$dp[i][j] = (dp[i - 1][0] + dp[i -1][1] + \cdots + dp[i - 1][j] + dp[i - 1][j + 1]) - dp[i - 1][j + 1] \\= dp[i][j +1] - dp[i - 1][j + 1]$. 移项得$dp[i][j + 1] = dp[i][j] + dp[i - 1][j + 1]。 j\in (i -sum[i], cnt), j + 1 \in (i - sum[i] - 1, cnt - 1)$.

再令$j = j -1$，得$dp[i][j] = dp[i][j-1] + dp[i - 1][j]$, 这样就可以去掉一层循环，复杂度为$O(n^2)$。

不过这是前缀优化，也就是要使$dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$，需要满足所有的$dp[i][j] = \sum\limits_{k = 0}^j dp[i - 1][k]$.由于上述提供的写法仅当$j\in [(i - sum[i]), cnt]$时才满足$dp[i][j] = \sum\limits_{k = 0}^{j} dp[i - 1][k]$, 所以$dp[i][j] = dp[i - 1][j] + dp[i][j - 1]$的转移并不完全合法。 不过我们可以用类似的方法来优化：

• 定义$pre[j]$表示$\sum\limits_{k = 1}^{j} dp[i - 1][k]$。
• 当$j \in [0, i - sum[i -1]]$时， $pre[j] = 0$。
• 当$j \in [(i - sum[i]), cnt]$时，$pre[j] = pre[j - 1] + dp[i - 1][j]$。
• 那么当$j \in [(i - sum[i]), cnt]， dp[i][j] = pre[j]$。 这样时间复杂度就可以优化到$O(n^2)$了。

提交代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 5e3 + 10, mod = 1e9 + 7;
string s;
int dp[N][N], sum[N], pre[N], nex[N];

int calc(int cnt, bool flag)
{
	if(!cnt) return 1;
	memset(dp, 0, sizeof dp);
	memset(sum, 0, sizeof sum);
	memset(pre, 0, sizeof pre);
	
	if(!flag)
	{
		reverse(s.begin(), s.end());
		for(int i = 0; i < s.size(); i++)
		{
			if(s[i] == ')') s[i] = '(';
			else s[i] = ')';
		}
	}
	
	int n = 0, now = 0;
	for(int i = 0; i < s.size(); i++)
	{
		if(s[i] == ')') sum[++n] = now;
		if(s[i] == '(') now++;
	}
	
	if(sum[1] > 0) dp[1][0] = 1, pre[0] = 1;
	for(int i = 1; i <= cnt; i++) dp[1][i] = 1, pre[i] = pre[i - 1] + 1;
	
	for(int i  = 2; i <= n; i++)
	{
		for(int j = 0; j <= cnt; j++) nex[j] = 0;
		for(int j = max(0ll, i - sum[i]); j <= cnt; j++)
		{
			dp[i][j] = pre[j];
			if(j - 1 < 0) nex[j] = dp[i][j];
			else nex[j] = (nex[j - 1] + dp[i][j]) % mod;
		}
		for(int j = 0; j <= cnt; j++) pre[j] = nex[j];
	}
	return dp[n][cnt];
}
void solve()
{
	cin >> s;
	int tot  = 0, cnt1 = 0, cnt2 = 0;
	for(auto x : s)
	{
		if(x == '(') tot++;
		else tot--;
		if(tot < 0) cnt1++, tot = 0;
	}
	cnt2 = tot;
	cout << calc(cnt1, 1) * calc(cnt2, 0) % mod << "\n";
}
signed main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(0);
	int t = 1;
	while(t--) solve();
	return 0;
}