简答题 偏难
#22121

2、括号序列

2、括号序列


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include &lt;bits/stdc++.h&gt; #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", &amp;n, &amp;k);     scanf("%s", S + 1);          // 初始化边界     for (int i = 1; i &lt;= n; ++i) {         dp[i][i - 1][0] = 1;     }          // 枚举区间长度     for (int len = 1; len &lt;= n; ++len) {         // 枚举左右端点         for (int i = 1, j = i + len - 1; j &lt;= n; ++i, ++j) {             // 处理长度不超过k的*或?序列             if (len &lt;= k &amp;&amp; dp[i][j - 1][0] &amp;&amp; (S[j] == '*' || S[j] == '?')) {                 dp[i][j][0] = 1;             }                          // 用子区间转移(长度至少为2才有意义)             if (len &gt;= 2) {                 // 判断左右端点是否为匹配的括号                 if ((S[i] == '(' || S[i] == '?') &amp;&amp; (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 &lt;= 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 &lt;bits/stdc++.h&gt; 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", &amp;n, &amp;k);     scanf("%s", s + 1); // 字符串从下标1开始存储     // 初始化:空区间是合法的*串(用于后续转移)     for (int i = 1; i &lt;= n; ++i) {         dp[i][i - 1][0] = 1;     }     // 枚举区间长度     for (int len = 1; len &lt;= n; ++len) {         // 枚举左端点i,右端点j = i + len - 1         for (int i = 1, j = i + len - 1; j &lt;= n; ++i, ++j) {             // 状态0:*串,长度&lt;=k,且j位置可填*或?,且[i,j-1]是*串             if (len &lt;= k &amp;&amp; dp[i][j - 1][0] &amp;&amp; (s[j] == '*' || s[j] == '?')) {                 dp[i][j][0] = 1;             }             // 长度至少为2时,处理其他状态             if (len &gt;= 2) {                 // 状态1:(A)形式,判断i和j是否可作为括号                 if ((s[i] == '(' || s[i] == '?') &amp;&amp; (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 &lt; 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>
这道题暂未补解析。