BRACKET – SPOJ

Đề bài: http://vn.spoj.com/problems/BRACKET/

Thuật toán:

• (đang cập nhập)

Code:

uses    math;
const   fi='';
        fo='';
        maxn=60+1;
var     f       :array[0..maxn,0..maxn,0..maxn] of int64;
        i,j,n,k :longint;
        s       :string;
        res,ans     :int64;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n,k);
        readln(s);
        close(input);
end;
function tinh(i,c,maxc:longint):int64;
var     sl      :int64;
begin
        if f[i,c,maxc]>-1 then exit(f[i,c,maxc]);
        if i>n then
                if (maxc=k) and (c=0) then
                        exit(1)
                else
                        exit(0);
        sl := 0;
        if c0 then sl := sl + tinh(i+1,c-1,max(maxc,c-1));
        f[i,c,maxc]:=sl;
        exit(sl);
end;
function lan(i,c,maxc:longint):longint;
begin
        if i>n then
                begin
                        inc(ans,1);
                        writeln(ans);
                        halt;
                end;
        if s[i]='(' then lan(i+1,c+1,max(maxc,c+1))
        else    ans := ans+ tinh(i+1,c+1,max(maxc,c+1));
        if s[i]=')' then lan(i+1,c-1,max(maxc,c-1));
end;
procedure process;
var     i,j,jj  :longint;
begin
assign(output,fo);rewrite(output);
        for i:=0 to n+1 do
                for j:=0 to k+1 do
                        for jj:=0 to k+1 do
                                f[i,j,jj]:=-1;
        res := tinh(1,0,0);
        writeln(res);
        ans := lan(1,0,0);
close(output);
end;
procedure print;
begin
end;
begin
        enter;
        process;
        print;
end.