牛客网NOIP赛前集训营-普及组（第一场）

C 括号

题目大意：对于输入的一串括号“()))(()()((”，可以删去若干位（删除位置不完全相同时均算作两种操作），若想最终得到合法括号串，求共有多少种操作方法可选。

先说算法后解释： 

dp[i][j]表示，加入第i个元素后，能将前i个字符转化为有j个未配对左括号‘（’的方法数。                                                                      以此为基础

dp[i][j] 的构成分为两部分，可根据操作中是否删去新字符来分类：                                                                                            不删，沿用dp[i-1][j]的方法即可；删去，则沿用dp[i-1][j-1]或dp[i-1][j+1]

对于0<j<n

若s[i]=='(' ，则dp[i][j]=dp[i-1][j]+dp[i-1][j-1]

若s[i]==')' ，则dp[i][j]=dp[i-1][j]+dp[i-1][j+1]

据此，每加入新字符，均对dp数组进行一次O(n)的更新，总复杂度O(n^2)

可进行空间优化，注意一下遍历的起始位置即可。附代码：

#include<iostream>
#include<cstdio>
#define ll long long

using namespace std;

const int mod=1e9+7;

int dp[10000+4];
char s[10000+4];
int n;

int main()
{
    cin>>n;
    scanf("%s",s+1);

    dp[0]=1;
    for(int i=1; i<=n; i++)
    {
        if(s[i]=='(')
        {
            for(int j=i-1; j>=0; j--)
                dp[j+1]=(dp[j+1]+dp[j])%mod;
        }
        else
        {
            for(int j=1; j<=i; j++)
                dp[j-1]=(dp[j-1]+dp[j])%mod;
        }
    }
    cout<<(dp[0]-1+mod)%mod<<endl;
    return 0;
}

思路：暴力枚举肯定无法应对（n==1000）的情况，考虑优化时努力向dp上靠拢。我们可以先观察对于一个子串（1~i），在其后加上一个括号‘（’或‘）’时，与旧字符串有什么关系。