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.