fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N=1e3+5;
  5. ll mod=1e9+7;
  6. string s;
  7. ll dp[N][N];
  8. ll cnt(int a,int b){
  9.     if(s[a]=='?'&&s[b]=='?')return 3;
  10.     if((s[a]=='{'||s[a]=='?')&&(s[b]=='}'||s[b]=='?'))return 1;
  11.     if((s[a]=='['||s[a]=='?')&&(s[b]==']'||s[b]=='?'))return 1;
  12.     if((s[a]=='('||s[a]=='?')&&(s[b]==')'||s[b]=='?'))return 1;
  13.     return 0;
  14. }
  15.  
  16. ll dq(int l,int r){
  17.     if(l>r)return 1;
  18.     if((r-l)%2==0)return 0;
  19.     if(dp[l][r]!=-1)
  20.         return dp[l][r];
  21.  
  22.     ll ans=0;
  23.     for(int i=l+1;i<=r;i++){
  24.         ans+=dq(l+1,i-1)*dq(i+1,r)*cnt(l,i);
  25.         ans%=mod;
  26.     }
  27.     return dp[l][r]=ans;
  28. }
  29.  
  30. int main(){
  31.     memset(dp,-1,sizeof(dp));
  32.     cin>>s;
  33.     s='a'+s;
  34.     cout<<dq(1,(int)s.length()-1)<<endl;
  35. }
  36.  
Success #stdin #stdout 0.01s 11532KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/6soAuc
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!