abc312d <dp, 括号匹配方案数>
题目
D - Count Bracket Sequences
思路
dp[i][j]为考虑前\(i\)个位置，待匹配的(有\(j\)个的方案数；
代码
点击查看代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
const int N = 3010, mod = 998244353;
LL dp[N][N];
void solv()
{
string s; cin >> s; s = "$" + s;
int n = s.size() - 1;
dp[0][0] = 1;
for (int i = 1; i <= n; i ++)
{
for (int j = 1; j <= i; j ++)
{
if (s[i] == '(') dp[i][j] += dp[i-1][j - 1];
else if (s[i] == ')') dp[i][j-1] += dp[i-1][j];
else
{
dp[i][j] += dp[i-1][j - 1];
dp[i][j-1] += dp[i-1][j];
}
dp[i][j] %= mod;
dp[i][j-1] %= mod;
}
}
cout << dp[n][0] << endl;
}
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int T = 1;
// cin >> T;
while (T --)
{
solv();
}
return 0;
}