http://acm.pku.edu.cn/JudgeOnline/problem?id=1141

Код:
program PKU1141;
const maxn = 101;

type integer = longint;

var f: array[0..maxn, 0..maxn] of integer;
    g: array[0..maxn, 0..maxn] of string;
    n: integer;
    st: string;

procedure prepare;
begin
  readln(st);
  n := length(st);
end;

procedure main;
var i, j, k, u, v, p: integer;
begin
  fillchar(f, sizeof(f), 0);
  for i := 1 to n do begin
    f[i, i] := 2; f[i, i - 1] := 0;
    if st[i] in ['[', ']'] then g[i, i] := '[]' else g[i, i] := '()';
    g[i, i - 1] := '';
  end;
  for i := 1 to n - 1 do
    for j := 1 to n - i do begin
      u := j; v := i + j;
      f[u, v] := n * 10;
      if (st[u] = '[') and (st[v] = ']') or (st[u] = '(') and (st[v] = ')') then begin
        f[u, v] := f[u + 1, v - 1] + 2;
        g[u, v] := st[u] + g[u + 1, v - 1] + st[v];
      end; p := 0;
      for k := u to v - 1 do
        if f[u, k] + f[k + 1, v] < f[u, v] then begin
          f[u, v] := f[u, k] + f[k + 1, v];
          p := k
        end;
      if p > 0 then g[u, v] := g[u, p] + g[p + 1, v];
    end;
  writeln(g[1, n]);
end;

begin
  prepare;
  main;
end.