网站开发亿玛酷给力5,嘉兴企业做网站,网站开发组岗位,网站建设公司浩森宇特文章目录 [Count Bracket Sequences](https://atcoder.jp/contests/abc312/tasks/abc312_d)问题建模问题分析1.分析合法括号字符串的特点2.从集合角度分析字符串每个字符的作用代码 Count Bracket Sequences 问题建模
给定一个字符串#xff0c;字符串内仅有3种字符#xff… 文章目录 [Count Bracket Sequences](https://atcoder.jp/contests/abc312/tasks/abc312_d)问题建模问题分析1.分析合法括号字符串的特点2.从集合角度分析字符串每个字符的作用代码 Count Bracket Sequences 问题建模
给定一个字符串字符串内仅有3种字符‘(’‘)’‘?’其中’?字符可以变为另外两种字符的其中一种问最多可以产生多少个合法的括号字符串。
问题分析
1.分析合法括号字符串的特点
合法的字符串其左右括号个数一定相等且对于任意一个位置的左括号数量一定大于等于右括号数量。
2.从集合角度分析字符串每个字符的作用
若当前字符可为左括号则每个集合内字符串左括号个数1,若当前字符可以为右括号则每个集合内字符串左括号个数-1。
则用DP动态维护集合设 f ( i , j ) f(i,j) f(i,j)为到字符i左括号个数为j的集合的个数转移方式根据当前字符进行或者-的转移。
代码
#includebits/stdc.h#define x first
#define y second
#define C(i) str[0][i]!str[1][i]
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
typedef pairint, int PII;
typedef pairLL, LL PLL;
const int N 3100, Mod 998244353;
int dp[N][N];void solve() {string str;cin str;int nstr.size();dp[0][0]1;for(int i0;in;i){for(int j0;jn;j){///为左括号时if(str[i]!)) dp[i1][j1](dp[i1][j1]dp[i][j])%Mod;///为右括号时if(j!0str[i]!() dp[i1][j-1](dp[i1][j-1]dp[i][j])%Mod;}}cout dp[n][0] \n;
} int main() {int t 1;//cin t;while (t--) solve();return 0;
}
