本人代码test019挂了,其他都过了。
显示:
AC * 23
WA * 1
代码:
# include <bits/stdc++.h>
using namespace std;
# define ll long long
# define N 3005
# define mod 998244353
int n;
ll dp[N][N];
// dp[i][j] 表示到第 i 位有 j 个未被配对的左括号的总方案数量
string Tmp;
char s[N];
signed main() {
cin >> Tmp;
int n = Tmp.size();
if (n == 0) {
cout << 1 << endl;
}
for (int i = 0; i < n; ++i) {
s[i + 1] = Tmp[i];
}
if (n & 1) {
cout << 0 << endl;
return 0;
}
if (s[1] == ')') {
cout << 0 << endl;
}
memset (dp, 0, sizeof dp);
dp[1][1] = 1;
for (int i = 2; i <= n; ++i) {
if (s[i] == '(') {
dp[i][0] = 0;
for (int j = 0; j <= i; ++j)
dp[i][j + 1] = dp[i - 1][j];
} else if (s[i] == ')') {
for (int j = 1; j <= i; ++j) {
dp[i][j - 1] = dp[i - 1][j];
}
} else {
for (int j = 0; j <= i; ++j) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j + 1];
dp[i][j] %= mod;
}
}
}
cout << dp[n][0] % mod << endl;
return 0;
}