简答题
偏难
#22121
2、括号序列
2、括号序列



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 550, mo = 1e9 + 7;
LL dp[N][N][5];
int n, k;
char S[N];
signed main() {
scanf("%d%d", &n, &k);
scanf("%s", S + 1);
// 初始化边界
for (int i = 1; i <= n; ++i) {
dp[i][i - 1][0] = 1;
}
// 枚举区间长度
for (int len = 1; len <= n; ++len) {
// 枚举左右端点
for (int i = 1, j = i + len - 1; j <= n; ++i, ++j) {
// 处理长度不超过k的*或?序列
if (len <= k && dp[i][j - 1][0] && (S[j] == '*' || S[j] == '?')) {
dp[i][j][0] = 1;
}
// 用子区间转移(长度至少为2才有意义)
if (len >= 2) {
// 判断左右端点是否为匹配的括号
if ((S[i] == '(' || S[i] == '?') && (S[j] == ')' || S[j] == '?')) {
dp[i][j][1] = (dp[i + 1][j - 1][0] + dp[i + 1][j - 1][2] +
dp[i + 1][j - 1][3] + dp[i + 1][j - 1][4]) % mo;
}
// 枚举子区间的断点
for (int t = i; t <= j - 1; ++t) {
dp[i][j][2] = (dp[i][j][2] + dp[i][t][3] * dp[t + 1][j][0]) % mo;
dp[i][j][3] = (dp[i][j][3] + (dp[i][t][2] + dp[i][t][3]) * dp[t + 1][j][1]) % mo;
dp[i][j][4] = (dp[i][j][4] + dp[i][t][0] * dp[t + 1][j][3]) % mo;
}
}
// 合并状态
dp[i][j][3] = (dp[i][j][3] + dp[i][j][1]) % mo;
}
}
printf("%lld", dp[1][n][3]);
return 0;
}</pre><pre class="brush:cpp;toolbar:false">//参考代码2
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 550;
const int MOD = 1e9 + 7;
int n, k;
char s[N];
LL dp[N][N][5]; // dp[i][j][0~4] 分别对应不同状态
int main() {
scanf("%d%d", &n, &k);
scanf("%s", s + 1); // 字符串从下标1开始存储
// 初始化:空区间是合法的*串(用于后续转移)
for (int i = 1; i <= n; ++i) {
dp[i][i - 1][0] = 1;
}
// 枚举区间长度
for (int len = 1; len <= n; ++len) {
// 枚举左端点i,右端点j = i + len - 1
for (int i = 1, j = i + len - 1; j <= n; ++i, ++j) {
// 状态0:*串,长度<=k,且j位置可填*或?,且[i,j-1]是*串
if (len <= k && dp[i][j - 1][0] && (s[j] == '*' || s[j] == '?')) {
dp[i][j][0] = 1;
}
// 长度至少为2时,处理其他状态
if (len >= 2) {
// 状态1:(A)形式,判断i和j是否可作为括号
if ((s[i] == '(' || s[i] == '?') && (s[j] == ')' || s[j] == '?')) {
dp[i][j][1] = (dp[i + 1][j - 1][0] + dp[i + 1][j - 1][2] +
dp[i + 1][j - 1][3] + dp[i + 1][j - 1][4]) % MOD;
}
// 枚举断点t,拆分区间为[i,t]和[t+1,j]
for (int t = i; t < j; ++t) {
// 状态2:A*B,A是状态3,B是状态0
dp[i][j][2] = (dp[i][j][2] + dp[i][t][3] * dp[t + 1][j][0]) % MOD;
// 状态3:A*B,A是状态2或3,B是状态1;或直接由状态1转移(后续会加)
dp[i][j][3] = (dp[i][j][3] + (dp[i][t][2] + dp[i][t][3]) * dp[t + 1][j][1]) % MOD;
// 状态4:A*B,A是状态0,B是状态3
dp[i][j][4] = (dp[i][j][4] + dp[i][t][0] * dp[t + 1][j][3]) % MOD;
}
// 状态3还可由自身的状态1转移而来(总合法状态包含(A)形式)
dp[i][j][3] = (dp[i][j][3] + dp[i][j][1]) % MOD;
}
}
}
// 最终答案:整个区间[1,n]的合法超级括号序列数量(状态3)
printf("%lld\n", dp[1][n][3]);
return 0;
}</pre><p></p>
这道题暂未补解析。