考虑这样的匹配问题,可以想如何确定第一次匹配,这样可以不重不漏地计数。
考虑 dp 的时候同时维护有几个括号没有匹配,匹配到 \(s\) 的第几位,所以令 \(f(i,j,k)\) 表示 dp 到(要计数的序列的)第 \(i\) 个字符,有 \(j\) 个左括号没有匹配,匹配到 \(s\) 的第 \(k\) 位。
转移很容易,考虑对每个 \(i,j\) 和 \(k(k<|s|)\),有两种转移(刷表法):
\[\begin{aligned} &f(i+1,j+1,to_{k,0}) \gets f(i,j,k)\quad (s_{i+1}=\texttt{(}) \\ &f(i+1,j-1,to_{k,1}) \gets f(i,j,k)\quad (s_{i+1}=\texttt{)}) \end{aligned} \]初始值为 \(f(0,0,0)=1\)。
其中 \(to_{k,0/1}\) 为当匹配到 \(s\) 的第 \(k\) 位时,下一位分别为两种括号的最长匹配,求法有两种:kmp 跳失配指针 或者 直接字符串比较暴力求。
对答案有贡献的即为 \(f(i,j,m)\),但是后面还有 \(2n-i\) 位没有确定,这时只需要乘上 右括号比左括号多 \(j\) 个且每个左括号都能匹配的括号序列个数即可,可以用卡特兰数,也可以直接 dp。
考虑 dp:设 \(g_{i,j}\) 为右括号比左括号多几个,显然 \(j\geq 0\),转移为:
\[\begin{aligned} &g(i+1,j+1) \gets g(i,j) \\ &g(i+1,j-1) \gets g(i,j) (j\geq 0) \end{aligned} \]初始值为 \(g(0,0)=1\)。
总复杂度瓶颈在 \(f\) 的 dp 上,为 \(O(n^3)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 205, p = 1e9 + 7;
int f[N][N][N], g[N][N], to[N][2], n;
char s[N];
bool eq(int len, int x, int y)
{
for(int i = x, j = y; i < x + len; i ++, j ++)
if(s[i] != s[j]) return 0;
return 1;
}
signed main()
{
ios::sync_with_stdio(0);cin.tie(0);
cin >> n >> s + 1;
int m = strlen(s + 1);
for(int i = 0; i < m; i ++)
for(int j = 0; j <= i; j ++)
for(int k : {0, 1})
if(s[j + 1] == k + 40 && eq(j, 1, i - j + 1))
to[i][k] = j + 1;
g[0][0] = 1;
for(int i = 0; i < n * 2; i ++)
for(int j = 0; j <= n; j ++)
{
g[i + 1][j + 1] = (g[i + 1][j + 1] + g[i][j]) % p;
if(j) g[i + 1][j - 1] = (g[i + 1][j - 1] + g[i][j]) % p;
}
f[0][0][0] = 1;
for(int i = 0; i < n * 2; i ++)
for(int j = 0; j <= n; j ++)
for(int k = 0; k < m; k ++)
for(int u : {0, 1})
{
int c = u ? -1 : 1;
if(j + c >= 0) f[i + 1][j + c][to[k][u]] = (f[i + 1][j + c][to[k][u]] + f[i][j][k]) % p;
}
int ans = 0;
for(int i = 1; i <= n * 2; i ++)
for(int j = 0; j <= n; j ++)
ans = (ans + 1ll * g[n * 2 - i][j] * f[i][j][m]) % p;
cout << ans;
return 0;
}
标签:gets,匹配,CF1015F,int,题解,括号,aligned,dp
From: https://www.cnblogs.com/adam01/p/18323461