PKU 1141 Brackets Sequence

http://poj.org/problem?id=1141
2種類の括弧で構成された文字列が入力される。
括弧を挿入して、長さが最小で括弧の対応がとれている文字列を出力しろというような問題。

昨日のTopCoder SRM 521 Div1Easy を解き終わった後に、解法がやっとこさ思いついた問題。
ただ、recでstringを返すようにしたらTLEが全然無くなってくれないので、多少面倒がりながら、経路復元的なものに書き換えました。

int memo[100][101];
int vis[200][200];
char in[200];

string p2ps[128];
int rec(int s,int e){
  if(s>=e)return 0;
  if(vis[s][e])return memo[s][e];
  vis[s][e]=true;
  int & ret=memo[s][e]=(e-s)*2;


  if(in[s]=='(' && in[e-1]==')')
    ret=min(ret,2+rec(s+1,e-1));
  
  if(in[s]=='[' && in[e-1]==']')
    ret=min(ret,2+rec(s+1,e-1));    

  for(int i=s+1;i<e;++i)
    ret=min(ret,
            rec(s,i)+rec(i,e));
  return ret;
}

void pr(int s,int e){
  if(s>=e)return;
  if(s+1==e){
    cout<<p2ps[in[s]];
    return;
  }
  if(in[s]=='(' && in[e-1]==')' && memo[s][e]==2+rec(s+1,e-1)){
    putchar('(');
    pr(s+1,e-1);
    putchar(')');
    return;
  }

  if(in[s]=='[' && in[e-1]==']' && memo[s][e]==2+rec(s+1,e-1)){
    putchar('[');
    pr(s+1,e-1);
    putchar(']');
    return;
  }

  for(int i=s+1;i<e;++i)
    if(memo[s][e]==rec(s,i)+rec(i,e)){
      pr(s,i);
      pr(i,e);
      return;
    }
}

int  main(){
  scanf("%s",in);
  p2ps['(']="()";
  p2ps[')']="()";
  p2ps['[']="[]";
  p2ps[']']="[]";
  rec(0,strlen(in));
  pr(0,strlen(in));
  puts("");
}