SRM686 Div1 Easy BracketSequenceDiv1

問題概要

()と[]からなる文字列が与えらます。複数個の括弧を取り除いて(取り除かなくても良いが、すべての括弧を取り除くことは不可)、対応が取れた括弧文字列の作り方の総数を求めよ。
例:
()[]
(), [], ()[]が作れるので3通り

())
真ん中or右端の括弧を取ると()が作れるので2通り

解法

区間dpで、[l, r]の文字列から、括弧の対応が取れた文字列の作り方の総数をメモ化再帰で求めていきます。かつ、S[l]とS[mid]の括弧が対応が取れている場合、そこから更に再帰で(l,mid-1) * (mid+1, r)を求めます。
また、[l,r]のうち前半部分で使用しない括弧があることもあるので、lを少しずつずらして再帰させる必要があります。
問題文の定義にあるように空文字列も括弧の対応が取れたものとみなして求めていきますが、すべてを取り除いたものは不可なので、最後にその分を差し引きます。

ソース

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>

using namespace std;

#define MAX_N 41

typedef long long int LL;
int N;
string S;
LL dp[MAX_N][MAX_N];

class BracketSequenceDiv1 {
public:

  LL solve(int l = 0, int r = N-1){

    if(dp[l][r] != -1)
      return dp[l][r];

    if(l >= r)
      return dp[l][r] = 1;
    
    LL ret = 0;
    for(int ll = l; ll <= r; ll++){
      for(int mid = ll+1; mid <= r; mid++){
	//対応が取れている場合
	if((S[ll] == '(' && S[mid] == ')') ||
	   (S[ll] == '[' && S[mid] == ']')){
	  ret += solve(ll+1, mid-1) * solve(mid+1, r);
	}
      }
    }
    
    //[l,r]の括弧をすべて取り除いた場合も対応が取れた括弧列とみなすので
    //1を足す
    return dp[l][r] = ret+1;
    
  }

  long long count(string _s) {

    S = _s;
    N = _s.length();
    
    memset(dp, -1, sizeof(dp));

    //すべての括弧を取り除いたものも数えてしまっているので、それは排除する
    return solve()-1;
    
  }
};