出题人题解 | #愤怒#

原题解链接：https://ac.nowcoder.com/discuss/149984

首先发现

如果选出来的那一部分匹配的话,那么剩下的也一定匹配

那么问题就是求括号匹配序列的方案

设$dp[i][j]dp[i][j]$表示前$ii$个括号,选取序列左括号比右括号多了$jj$个

那么转移就好写了

$f[i][j]=f[i-1][j+-1]+f[i][j]f[i][j]=f[i-1][j+-1]+f[i][j]$

枚举$jj$转移然后滚掉一维

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <queue>
#include <cstdlib>
#include <cstring>
using namespace std;  
inline int read() {     
    int x = 0,f = 1; 
    char c = getchar(); 
    while(c < '0' || c > '9') c = getchar(); 
    while(c <= '9' && c >= '0') x = x * 10 + c - '0',c = getchar(); 
    return x * f ;
} 
const int maxn = 100007;  
#define mod 2333
int f[maxn * 2], n , sum; 
char s[maxn]; 
int main()  { 
	/*for(int test = 1; test <= 10; test++) {
    char s1[10] , in[10] = ".in", s1name[10] = "a";
    char s2[10] , out[10] = ".out", s2name[10] = "a";
    sprintf(s1, "%d", test); strcat(s1, in); strcat(s1name, s1);
    sprintf(s2, "%d", test); strcat(s2, out);strcat(s2name, s2);
    freopen(s1name, "r", stdin);
    freopen(s2name, "w", stdout); */
	n = read(); 
    scanf("%s",s+1); 
    //printf("%d\n",strlen(s + 1)); 
	//return 0; 
	memset(f,0,sizeof f); 
	n = strlen(s + 1);
	sum = f[1] = 1; 
    for(int i = 1;i <= n && sum > 0;++ i) {  
        int x = 0; 
        sum += s[i] == '(' ? 1 : -1; 
        if(s[i] == ')')
            for(int j = 1;j <= sum;++ j)
                f[j] = (f[j + 1] + f[j]) % mod; 
        else   
            for(int j = sum;j >= 1;-- j) 
                f[j] = (f[j - 1] + f[j]) % mod;  
        f[sum + 1] = 0; 
    } 
    if(sum != 1)  {    
        puts("0");return 0;    
    } 
    printf("%d\n",f[1]);  
	//} 
    return 0; 
} 
/*
如果一部分匹配
剩下的也一定匹配
那么就是求括号匹配序列的方案书
设dpf[i][j]表示枚举到i，左括号比右括号多j
那么转移就是
f[i][j] = f[i - 1][j - x] + f[i - 1][j] 
滚掉一纬数组 

*/