这是一道区间 dp，思维难度与实现难度都不小，主要的瓶颈在于如何不重不漏地转移（这要求仔细地读题）。
和题目一样，A 表示一个符合规范的超级括号序列，S 表示任意一个仅由不超过 $k$ 个字符 * 组成的非空字符串，即 *...*。以下就不再赘述字符的含义。
先将状态分成以下几类：
$dp_{i,j,0}$ 表示 $[i,j]$ 的符合规范的超级括号序列的数量
$dp_{i,j,1}$ 表示 $[i,j]$ 的符合 (A) 的形式的数量
$dp_{i,j,2}$ 表示 $[i,j]$ 的符合 SA 的形式的数量
$dp_{i,j,3}$ 表示 $[i,j]$ 的符合 AS 的形式的数量
接下去就是状态转移的过程。
先预处理出一个布尔数组 $g$，若 $g_{i,j} = 1$ ，那么有 $[i,j]$ 为一个 $S$ 串。
对于 (A) 的形式，可以由 *...*，SA，AS 和 A 加上一对左右括号即可得到。也就是说若 $[i,j]$ 满足 (A) 的形式，也就有原字符串的第 $i$ 位为 ( 或 ?，第 $j$ 位为 ) 或 ?。转移为 $dp_{i,j,1} = g_{i + 1,j - 1} + dp_{i + 1,j - 1,0} + dp_{i + 1,j - 1,2} + dp_{i + 1,j - 1,3}$。相信大家读到这里会有一个疑问，若 $i + 1 = j$，那么会有 $i + 1 > j - 1$，导致答案出错。很简单，由于 () 也合法，所以只需要进行一个特判即可。
对于 SA 的形式，由一段 S 和 A 组成，一次设置 $[i,j]$ 的断点 $k$ 来进行转移。转移方程为 $dp_{i,j,2} = \sum_{k = i}^{r - 1} g_{i,k} \times dp_{j + 1,r,2}$。只有在 $[i,k]$ 是 S 串时才可以被转移，用乘法便很好的解决了这个问题。
对于 AS 的形式大致与上一个相同，转移方程为 $dp_{i,j,3} = \sum_{k = i}^{r - 1} g_{k + 1,r} \times dp_{i,k,3}$。
最后是 $dp_{i,j,0}$ 的转移。$dp_{i,j,1}$ 肯定符合情况，之后需要通过两个小区间来得到大区间，也就是 AB 以及 ASB 的情况，但是需要考虑到重复计算的情况。直接令 A 串属于 (...) 的情况，这样就能去掉重复计算，因此有转移方程 $dp_{i,j,0} = dp_{i,j,1} + \sum_{k = i}^{r - 1} dp_{i,k,1} \times (dp_{k + 1,r,0} + dp_{k + 1,r,2})$。
因此最后的时间复杂度是 $O(n^3)$ 的，代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| #include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define init(x) memset (x,0,sizeof (x))
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
using namespace std;
const int MAX = 505;
const int MOD = 1e9 + 7;
int n,k;char str[MAX];
ll dp[MAX][MAX][4];bool g[MAX][MAX];
bool check (int x,int y);
int main ()
{
scanf ("%d%d%s",&n,&k,str + 1);
for (int i = 1;i <= n;++i)
{
for (int j = i;j <= n;++j)
{
if (j - i + 1 > k) break;
bool ok = 1;
for (int k = i;k <= j;++k)
if (str[k] != '*' && str[k] != '?') ok = 0;
if (ok) g[i][j] = 1;
}
}
for (int i = 1;i <= n;++i)
{
for (int l = 1;l <= n;++l)
{
int r = l + i;
if (r > n) break;
if (check (l,r))
{
if (l == r - 1) dp[l][r][1] = 1;
else dp[l][r][1] += (g[l + 1][r - 1] + dp[l + 1][r - 1][0] + dp[l + 1][r - 1][2] + dp[l + 1][r - 1][3]) % MOD;
}
dp[l][r][0] += dp[l][r][1];
dp[l][r][0] %= MOD,dp[l][r][1] %= MOD;
for (int k = l;k < r;++k)
{
dp[l][r][2] += g[l][k] * dp[k + 1][r][0];
dp[l][r][3] += dp[l][k][0] * g[k + 1][r];
dp[l][r][0] += dp[l][k][1] * (dp[k + 1][r][0] + dp[k + 1][r][2]) % MOD;
for (int p = 0;p < 4;++p) dp[l][r][p] %= MOD;
}
}
}
printf ("%lld\n",dp[1][n][0]);
return 0;
}
bool check (int x,int y) {return ((str[x] == '(' || str[x] == '?') && (str[y] == ')' || str[y] == '?'));}
|
