2021 CCF CSP-S2.括号序列

题目

4091. 括号序列

算法标签: 区间$dp$

思路

区间$dp$添加维表示形态$f[i][j][k]$, 对于每种形态考虑状态如何进行转移, 枚举的时候不能重复, 星号也要定义唯一的解析方式, 算法时间复杂度$O(n^3)$

代码

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;typedef long long LL;
const int N = 510, MOD = 1e9 + 7;int n, m;
string s;
int f[N][N][5];bool check(char a, char b) {return a == b || a == '?';
}int main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);cin >> n >> m >> s;for (int len = 1; len <= n; ++len) {for (int i = 0; i + len - 1 < n; ++i) {int j = i + len - 1;if (len == 1) {if (check(s[i], '*')) f[i][j][2] = 1;}else {if (check(s[i], '(') && check(s[j], ')')) {if (len == 2) f[i][j][0] = 1;for (int k = 0; k < 5; ++k) f[i][j][0] = (f[i][j][0] + f[i + 1][j - 1][k]) % MOD;}if (len <= m && check(s[i], '*')) f[i][j][2] = f[i + 1][j][2];// 枚举分界点for (int k = i; k < j; ++k) {auto t = f[i][j], l = f[i][k], r = f[k + 1][j];t[1] = (t[1] + (l[0] + (LL) l[1] + l[3]) * r[0]) % MOD;t[3] = (t[3] + (l[0] + (LL) l[1]) * r[2]) % MOD;t[4] = (t[4] + l[2] * (r[0] + (LL) r[1])) % MOD;}}}}int ans = ((LL) f[0][n - 1][0] + f[0][n - 1][1]) % MOD;cout << ans << "\n";return 0;
}