柱爷的恋爱

Time Limit: 1000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)

Submit  Status

她手里有刚刚收到从远方的括号序列(仅包含( ) [ ]的序列),然而序列已经是一团乱麻,不堪入目,柱爷看到她坐在位子掩面哭泣,便上前安慰一番,她向柱爷提出自己的"无理"申请.

她"蛮横"地要求柱爷计算出:删去这个括号序列的一个子集(不可以把整个括号序列都删去,那可是她的心爱之物;可以不完全删;子集可能是不连续的;子集可能为∅),使得这个括号序列合法的方案数.

这个方案数可能很大,所以她只要求柱爷计算出这个方案数00000007就好了(她心疼柱爷,不想让柱爷打高精度).

你能帮柱爷解决这个恋爱中的小小问题吗？

Input

第一行一个整数 N N，表示括号序列的长度

接下来一行包含一个长度为 N N的括号序列字符串

数据保证:

1≤N≤300 1≤N≤300

Output

一个正整数,表示柱爷要回答她的数.

Sample input and output

Sample Input Sample Output 4 ()[] 3 3 ()) 2

Hint

合法的括号序列定义如下:

如果S是合法序列,那(S)和[S]也是合法序列;如果A和B都是合法序列,那么AB也是合法序列.例如,下面的字符串都是合法序列:(), [], (()), ([]), ()[], ()[()]

Source

2016 UESTC Training for Dynamic Programming

题解：看到括号匹配问题，第一时间就想到是区间dp，但是有关方案数之间的关系想了好久，最后总算是想出来了，枚举每一对相匹配的括号，对于每一对括号，组合数是括号内的合法删除方案数*括号外的合法删除方案数，当i=j时，必然没有一对括号，因此必须要全部删除才合法

1.当i=j dp[i][j]=1;

2当i!=j &i,k为一对匹配括号，dp[i][j]=res+dp[i+1][k-1]+dp[k+1][j];

3其他情况 dp[i][j]=dp[i+1][j];

代码如下

#include <iostream> #include <bits/stdc++.h> using namespace std; char s[305]; typedef long long LL; LL dp[305][305]; LL solve(LL i,LL j) { if(dp[i][j]>=0) return dp[i][j]; if(i>=j) return 1; LL res=solve(i+1,j); char aim='0'; if(s[i]=='(') aim=')'; else if(s[i]=='[') aim=']'; if(aim!='0') { for(LL q=i+1;q<=j;q++) { if(s[q]==aim) res=max(res,res+solve(i+1,q-1)*solve(q+1,j))00000007; } } dp[i][j]=res; return res00000007; } int main() { long long n; cin>>n; for(LL i=0;i<=n;i++) { for(LL j=0;j<=n;j++) dp[i][j]=-1; } //c har s[305]; cin>>s; LL ans=solve(0,n-1)00000007-1; cout << ans << endl; return 0; }