首页 » 动态规划 » 正文

牛客网NOIP赛前集训营-普及组(第一场)括号

牛客网NOIP赛前集训营-普及组(第一场)括号

链接:传送门
来源:牛客网

题目描述

小A有一个只包含左右括号的字符串S。但他觉得这个字符串不够美观,因为它不是一个合法的括号串。一个合法的括号串是这样定义的:
1. ()是合法的括号串
2. 若A是合法的括号串,则(A)则是合法的括号串
3. 若A,B是合法的括号串,则AB也是合法的括号串。

小A现在希望删掉S中若干个字符,使得剩下的字符串是一个合法的括号串。小A想知道有多少不同的方案。两个方案是不同的,当且仅当他们删除的位置不同。比如当S是(()时,有两种方案。分别是删掉第一个位置,或是删掉第二个位置。

输入描述:

第一行一个整数n,代表S的长度。
第二行输入n个字符,字符要么是(,要么是)。代表串S。

输出描述:

一行一个整数,代表不同的方案数。答案对10^9+7取模。

示例1

输入
8
)(()(())

输出

30

备注:

20%: n <= 20
40%: n <= 100
60%: n <= 1000
100%: n <= 10000

解法

dp,因为n是1e4去了,所以要用滚动数组。令dp[i][j]表示前i个括号形成还有j个左括号没有匹配的方案种数。那么答案其实就是dp[n][0],最初将dp[0][0]赋值为1,最终的结果减去1,来得到结果。

代码

#include<bits/stdc++.h>

using namespace std; 
const int maxn = 10000+100; 
const int mod = 1e9+7; 
int main(){
    int n; 
    scanf("%d", &n); 
    char str[maxn]; 
    scanf("%s", str+1); 
    int dp[2][maxn]; 
    memset(dp, 0, sizeof(dp)); 
    int tot=0; //不能进行n次的计算,只能算有多少个左括号就算多少
    dp[0][0]=1; 
    for(int i=1; i<=n; i++){
        if(str[i] == '('){  //左括号
            tot++;  
            if(i%2){
                for(int j=tot; j>=1; j--){  //从1-tot也行,没啥影响
                    dp[1][j] = (dp[0][j-1] + dp[0][j]) % mod; 
                }
                dp[1][0] = dp[0][0]; //形成0个未匹配左括号需要另外搞一下
            }
            else {
                for(int j=tot; j>=1; j--){
                    dp[0][j] = (dp[1][j-1] + dp[1][j]) % mod; 
                }
                dp[0][0] = dp[1][0]; 
            }
        }
        else {  //右括号
            if(i%2){
                for(int j=0; j<=tot; j++){
                    dp[1][j] = (dp[0][j+1] + dp[0][j]) % mod; 
                }
            }
            else {
                for(int j=0; j<=tot; j++){
                    dp[0][j] = (dp[1][j+1] + dp[1][j]) % mod; 
                }
            }
        }
    }
    if(n % 2) printf("%d\n", dp[1][0]-1); 
    else printf("%d\n", dp[0][0]-1);  
}

发表评论