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.