BRACKET - Dãy ngoặc

Tác giả: flashmt

Ngôn ngữ: Pascal

var n,kk:longint;
    a:array[0..61] of longint;
    b:array[0..1,0..61,-1..31] of qword;
    c:array[0..61,-1..31] of qword;
    res,re:qword;

procedure rf;
var i,t:longint; c:char;
begin
     readln(n,kk);
     t:=0;
     for i:=1 to n do
     begin
          read(c);
          if c='(' then inc(t) else dec(t);
          a[i]:=t;
     end;
end;

procedure calc(z:longint);
var i,j,t,k:longint;
begin
     b[z,0,0]:=1; k:=kk-z;
     if k<1 then exit;
     for i:=1 to n div 2 do
     begin
          for j:=0 to i do
          begin
               if j<k then t:=j else t:=k;
               b[z,i,t]:=b[z,i-1,t-1]+b[z,i-1,t+1];
          end;
     end;
     for i:=n div 2 + 1 to n do
     begin
          for j:=0 to n-i do
          begin
               if j<k then t:=j else t:=k;
               b[z,i,t]:=b[z,i-1,t-1]+b[z,i-1,t+1];
          end;
     end;
end;

procedure pr;
var i,j,k:longint; kt:boolean;
begin
     fillchar(b,sizeof(b),0);
     calc(1); calc(0);
     for i:=0 to n do
         for j:=0 to kk do
             c[i,j]:=b[0,i,j]-b[1,i,j];
     re:=c[n,0];
     k:=1; res:=0;
     kt:=false;
     for i:=n-2 downto 2 do
     begin
          j:=a[n-i];
          if j>k then
          begin
               if not kt then res:=res+c[i,k-1]
               else res:=res+b[0,i,k-1];
          end;
          if j=kk then kt:=true;
          k:=j;
     end;
end;

procedure wf;
begin
     writeln(re);
     writeln(re-res);
end;

begin
     rf;
     pr;
     wf;
end.

Download