CodeForces - 629C Famil Door and Brackets (dp)-白红宇

CodeForces - 629C Famil Door and Brackets (dp)

阅读量：2135 次

发布时间：2019-04-30

本文共 1317 字，大约阅读时间需要 4 分钟。

题目大意：

给你一个长度为m的字符串，字符串中只有左括号'(' 和右括号 ')' ，你要加入一些括号使得字符串长度变为n 并且满足合法，合法的条件是

①左括号总数等于右括号总数

②并且要求在任意一位置左括号数量>= 右括号数量

问有多少对p，q能满足p+s+q

题解：

设dp[i][j]为前i个字符，左括号'('个数比有括号')'个数多j个的满足的pq对数

从i=0到n-m枚举p的位数，n-m-i就是q的位数，然后把两边p和q的可能情况相乘就是答案

因为p,q的每一位是‘(‘还是‘)‘不一定，两种情况都有可能，两种情况都要考虑，那么这样其实就与我们读入的s是没有关系的，我们可以提前处理出dp[i][j]的值来

这里还有一点，dp[i][j]和dp[i][-j]的值应该是一样的，因为完全可以把一个字符串的左右括号互换,互换之后就由dp[i][j]变成了dp[i][-j]

其余的详见注释叭

#include
   
    #include
    
     #define mod 1000000007#define INF 1000000007using namespace std;typedef long long ll;ll dp[2010][2010];int main(){    //freopen("input.txt","r",stdin);    int n,m;    string s;    cin>>n>>m;    cin>>s;    dp[0][0]=1;    for(int i=1;i<=2000;++i)    {        dp[i][0]=dp[i-1][1];        //dp[i][0]就是前i个左右括号个数相等((()))这样的        //那么第i个一定是右括号,所以一定是由dp[i-1][1]推过来        for(int j=1;j<=i;++j)        {            dp[i][j]=(dp[i-1][j-1]+dp[i-1][j+1])%mod;            //dp[i-1][j+1]-->dp[i][j]代表第i位上是(            //dp[i-1][j-1]-->dp[i][j]代表第i位上是)        }    }    int num=0;    int minn=INF;    for(int i=0;i
     
      len-i)continue;//右边可能存在的右括号个数不能大于        if(minn+j<0)continue; //  保证在任意一位置  左括号数量>= 右括号数量        ans+=(dp[i][j]*dp[len-i][j+num])%mod;        //j是左边p左括号大于右括号的数，sum是s中左括号大于右括号的数        //那么要满足条件p+s+q整体左括号=右括号数，则q必须是-(j+num)        ans%=mod;    }    cout<
      
       <