CF629C
题意
给定长度为 \(m\) 的仅含 ( 和 ) 的字符串，为其左右补上两个字符串使其达到指定长度 \(n\) 且合法, 需补足字符串合计长度 \(n - m\) 满足 \(n - m \le 2000\)。
解析
字符串合法条件为：
左右括号总数相等；
从左数起在任意位置上左括号数量不小于右括号数量。
首先思考下左侧的合法状况，设 \(f^1_{i,j}\) 为前 \(i\) 个字符使用了 \(j\) 个 ( 时的方案数，有 \(f^1_{0,0} = 1\)，得到状态转移方程为：
\[f^1_{i,j} = f^1_{i - 1, j - 1} + f^1_{i - 1, j}
\]
然后思考下另一侧，题意表明左右括号总数相等，且从左数起一定有左括号数 \(l\) 不小于右括号数 \(r\)，即
\[l \ge r
\]
可化成
\[\frac{n}{2} - l \le \frac{n}{2} - r
\]
即从右数起在任意位置上右括号数量不小于左括号数量。由此，可设 \(f^2_{p, q}\) 为从右数起前 \(p\) 个字符使用了 \(q\) 个 ) 时的方案数，状态转移方程同上。
最后，枚举左右状态并利用乘法原理即可算出答案，设需补足的右括号共为 \(tr\) 个，对于任意状态下都有 \(p = n - m - i\) 和 \(q = tr - (i - j)\)。
代码
#include<bits/stdc++.h>
#define LL long long
using namespace std;
vector<vector<LL> > dp1(2005, vector<LL>(2005, 0)), dp2(2005, vector<LL>(2005, 0));
LL mod = 1000000007;
//要开long long，不然#4可能会炸精度
signed main()
{
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
LL n, m, tl = 0, tr, nl = 0, nr = 0, ml = 0, mr = 0, ans = 0;
string s;
cin >> n >> m;
getline(cin, s);
getline(cin, s);
for (int i = 0; i < m; i++)
{
tl += s[i] == '(';
nl += 2 * (s[i] == ')') - 1; //计算当前右左括号数量差
ml = max(ml, nl); //存储最大差值
//左方插入字符串左右括号数量差至少达到ml
}
//反向遍历一次计算左右括号数量差值，作用同上
for (int i = m - 1; i > -1; i--)
{
nr += 2 * (s[i] == '(') - 1;
mr = max(mr, nr);
}
if (tl > n / 2 || m - tl > n / 2 || n & 1)
{
//将完全不合法的情况直接排除
cout << "0";
return 0;
}
tl = n / 2 - tl;
tr = n - m - tl;
//tl和tl分别表示外部插入字符串总共需要的左右括号数量
//计算左侧合法情况
dp1[0][0] = 1;
for (LL i = 1; i <= min(n - m, tl * 2); i++)
for (LL j = 0; j <= min(i, tl); j++)
if (i - j <= j && i - j <= tr)
dp1[i][j] = (dp1[i - 1][j - 1] + dp1[i - 1][j]) % mod;
//计算右侧合法情况
dp2[0][0] = 1;
for (LL i = 1; i <= min(n - m, tr * 2); i++)
for (LL j = 0; j <= min(i, tr); j++)
if (i - j <= j && i - j <= tl)
dp2[i][j] = (dp2[i - 1][j - 1] + dp2[i - 1][j]) % mod;
//乘法原理计算答案
for (int i = 0; i <= n - m; i++)
for (int j = 0; j <= i; j++)
if (j - (i - j) >= ml && tr - (i - j) - (tl - j) >= mr) //判断左右侧的左右括号数是否达到要求
ans = (ans + dp1[i][j] * dp2[n - m - i][tr - i + j]) % mod;
cout << ans;
}
最后祝各位顺利AC。 >w<