复赛二：括号序列(bracket)
洛谷：P7914
OJ: P5940
代码分析：
全局变量：
- 定义的
dp数组清晰表达了每种形态的意义，利用三维数组分别表示子区间的不同类型。
dp数组的初始化：对于单个字符的情况，dp[i][i-1][0]被初始化为1，因为空区间是合法的。
状态定义：
dp[l][r][0]：表示区间[l, r]是全由星号*组成的合法序列。dp[l][r][1]：表示区间[l, r]是由匹配的括号包围起来的合法序列，形如(S)，其中S是一个合法的子序列。dp[l][r][2]：表示区间[l, r]是由左边的括号和右边的星号*组成的合法序列，形如(S)*。dp[l][r][3]：表示区间[l, r]是合法的括号序列，形如(S)(S)，即左右两边都包含括号序列。dp[l][r][4]：表示区间[l, r]是由左边的星号*和右边的括号组成的合法序列，形如*(S)。dp[l][r][5]：表示区间[l, r]是由左右两边都是星号，且中间有括号组成的合法序列，形如*(S)*。
动态规划转移逻辑：
- 形态0：全是星号
*或问号?的序列，只能在长度不超过k时有效。通过检查前一个位置是否也是星号序列来递推。 - 形态1：如果当前子串两端是匹配的括号
(S)，则中间的子串可以是形态 0、2、3、4 中的任意一种。 - 形态2：区间 [i, j] 可以通过分割点
t将 [i, t] 作为形态(S)和 [t+1, j] 作为星号序列进行递推。 - 形态3：将形态
(S)通过分割点合并左右两边的括号序列。 - 形态4：处理以星号开头，右边为括号序列的情况。
最终输出：
- 最终我们输出
dp[1][n][3]，表示从位置 1 到 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 58 59 60 61 62 63 64 65 66 | /**************************************************************** * Description: 2021年提高组第二题 括号序列 * Author: Alex Li * Date: 2024-09-28 18:12:53 * LastEditTime: 2024-09-29 07:50:17 ****************************************************************/ #include <bits/stdc++.h> using namespace std; #define mod 1000000007 long long dp[510][510][6]; // dp[l][r][t] 表示从第 l 到第 r 个字符，形态 t 的合法序列数量 int main() { int n, k; string S; // 输入字符串长度 n 和最大连续 * 的数量 k cin >> n >> k; // 输入超级括号序列，并在前面加一个空格，使索引从 1 开始方便处理 cin >> S; S = ' ' + S; // S[0]为空，S[1]到 S[n] 是实际数据 // 初始化 dp 数组：单个字符的情况 // dp[i][i-1][0] = 1 表示空区间是合法的星号序列（形态 0） for (int i = 1; i <= n; i++) { dp[i][i-1][0] = 1; // 空区间是合法的，初始化为 1 } // 枚举子区间长度 len for (int len = 1; len <= n; ++len) { // 枚举区间的左端点 i 和右端点 j for (int i = 1, j = i + len - 1; j <= n; ++i, ++j) { // 处理形态 0：全为 * 或 ? 的合法区间，长度不能超过 k if (len <= k && dp[i][j-1][0] && (S[j] == '*' || S[j] == '?')) { dp[i][j][0] = 1; // 如果之前区间 [i, j-1] 是合法星号序列，并且 S[j] 是 * 或 ?，那么 [i, j] 也是合法的 } // 处理形态 1：左右端点为匹配的括号，即 (S) if (len >= 2 && (S[i] == '(' || S[i] == '?') && (S[j] == ')' || S[j] == '?')) { // 如果 S[i] 和 S[j] 能配对成括号，则中间部分可以是形态 0、2、3、4 的任意组合 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, j] 分割为两部分 [i, t] 和 [t+1, j] for (int t = i; t <= j-1; ++t) { // 处理形态 2：(S) + * 的形式 dp[i][j][2] = (dp[i][j][2] + dp[i][t][3] * dp[t+1][j][0]) % mod; // 处理形态 3：(S)(S) 的形式 dp[i][j][3] = (dp[i][j][3] + (dp[i][t][2] + dp[i][t][3]) * dp[t+1][j][1]) % mod; // 处理形态 4：*(S) 的形式 dp[i][j][4] = (dp[i][j][4] + dp[i][t][0] * dp[t+1][j][3]) % mod; } // 将形态 1 的结果加入形态 3，形态 3 代表完整的括号序列 dp[i][j][3] = (dp[i][j][3] + dp[i][j][1]) % mod; } } // 输出最终结果，形态 3 是完整的括号序列，从位置 1 到 n cout << dp[1][n][3] << endl; return 0; } |