TopCoder Statistics - Problem Statement
This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

$(, ), [, ], \{, \}$で構成される文字列を，$well\ formed$にするために，最小何回文字を変えることでできるか．$well\ formed$は以下のように定義される．

空文字列は$well\ formed$
$s$を$well\ formed$とした時に，$(s)$，$[s]$，$\{s\}$もまた$well\ formed$
$s, t$を$well\ formed$とした時，それを連結した文字列$st$も$well\ formed$

$$ dp[l][r] := 区間[l, r)をwell\ formedにするための最小回数 $$ とした．$2$番目の条件として区間$[l, r)$を見る場合，$s[l]$と$s[r-1]$が括弧として成立している場合はそのまま，片方違う場合は$+1$，それ以外は$+2$，して括弧を外す(区間$[l+1, r-1)$を見る)．
$3$番目の条件として，連結しても良いので，分ける場所を全探索する．必ず偶数長になるため，奇数長となる切り方はしないようにする．

Code

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int dp[55][55];
string s = "";

int f(int l, int r) {
  char a = s[l], b = s[r-1];
  if(a == '(' && b == ')') return 0;
  if(a == '{' && b == '}') return 0;
  if(a == '[' && b == ']') return 0;

  if(a == '(' || b == ')') return 1;
  if(a == '{' || b == '}') return 1;
  if(a == '[' || b == ']') return 1;

  return 2;
}

int dfs(int l, int r) {
  if(dp[l][r] != INF) return dp[l][r];
  if(l == r) return 0;
  int ret = INF, x = f(l, r);

  if(x == 0) ret = min(ret, dfs(l+1, r-1));
  else if(x == 1) ret = min(ret, dfs(l+1, r-1) + 1);
  else ret = min(ret, dfs(l+1, r-1) + 2);

  REP(i, l+1, r) {
      if((i - l) % 2 == 0) {
          ret = min(ret, dfs(l, i) + dfs(i, r));
      }
  }

  return dp[l][r] = ret;
}

class CorrectingParenthesization {
  public:
  int getMinErrors(string _s) {
      s = _s;
      int n = s.size();
      rep(i, 55) rep(j, 55) dp[i][j] = INF;

      return dfs(0, n);
  }
};

ry0u_ydのblog

SRM301 D2H CorrectingParenthesization

TopCoder Statistics - Problem Statement

Code