学步园

【题意】

给定一个括号序列，求最少添加多少个字符能够使其变成合法序列，输出方案

合法即是括号匹配

【输入】

一行一个字符串，不超过100位

【输出】

加入字符最少的合法方案

黑书P113页例题

算是动规入门题吧

首先n^3来求每一段需要最少加入几个字符

然后递归逆向求解

program poj1141;
var
  s:string;
  n,i,j,k:longint;
  f:array [0..101,0..101] of longint;

function min(a,b:longint):longint;inline;
begin
  if a<b then exit(a)
         else exit(b);
end;

function solve (l,r:longint):string;
var
  i:longint;
begin
  if l>r then exit('');
  if f[l,r]=f[l+1,r]+1 then
    if (s[l]='(')or(s[l]=')') then
      exit('()'+solve(l+1,r))
                              else
      exit('[]'+solve(l+1,r));
  if f[l,r]=f[l,r-1]+1 then
    if (s[r]='(')or(s[r]=')') then
      exit(solve(l,r-1)+'()')
                              else
      exit(solve(l,r-1)+'[]');
  if (r-l+1>=2)and(s[l]+s[l+1]='()')and(f[l,r]=f[l+2,r]) then
    exit('()'+solve(l+2,r));
  if (r-l+1>=2)and(s[l]+s[l+1]='[]')and(f[l,r]=f[l+2,r]) then
    exit('[]'+solve(l+2,r));
  if (s[l]+s[r]='()')and(f[l,r]=f[l+1,r-1]) then
    exit('('+solve(l+1,r-1)+')');
  if (s[l]+s[r]='[]')and(f[l,r]=f[l+1,r-1]) then
    exit('['+solve(l+1,r-1)+']');
  for i:=l to r-1 do
    if f[l,i]+f[i+1,r]=f[l,r] then exit(solve(l,i)+solve(i+1,r));
end;

begin
  readln(s);
  n:=length(s);
  for i:=1 to n do
    for j:=1 to n-i+1 do
      begin
        f[j,j+i-1]:=min(f[j+1,j+i-1],f[j,j+i-2])+1;
        if (s[j]+s[j+i-1]='()')or(s[j]+s[j+i-1]='[]') then
          f[j,j+i-1]:=min(f[j,j+i-1],f[j+1,j+i-2]);
        if (i>1)and((s[j]+s[j]='()')or(s[j]+s[j]='[]')) then
          f[j,j+i-1]:=min(f[j,j+i-1],f[j+2,j+i-1]);
        if (i>1)and((s[j+i-2]+s[j+i-1]='()')or(s[j+i-2]+s[j+i-1]='[]')) then
          f[j,j+i-1]:=min(f[j,j+i-1],f[j,j+i-3]);
        for k:=j to j+i-2 do
          f[j,j+i-1]:=min(f[j,j+i-1],f[j,k]+f[k+1,j+i-1]);
      end;
  writeln(solve(1,n));
 end.