ADBRACK – SPOJ

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

Thuật toán

• Bài này sử dụng phương pháp đệ quy có nhớ kết hợp với thuật toán xử lý số lớn
• Các bạn có thể đọc code bên dưới để hiểu hơn

Code:

const   fi='';
        fo='';
        maxn=100+3;
var     f       :array[-maxn..maxn,-maxn..maxn] of ansistring;
        i,j,n,k :longint;
        st      :ansistring;
        p       :longint;
        res     :ansistring;
        stack   :array[1..maxn] of char;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n,k);
        readln(st);
        close(input);
end;
procedure init;
begin
        for i:=0 to n+1 do
                for j:=0 to n+1 do f[i,j]:='-1';
end;
function cong (a,b: ansistring): ansistring;
var     nho,tam,i:longint;
        res     :ansistring;
begin
        while length(a)0 then res:='1'+res;
        exit(res);
end;
function tinh(i,c:longint):ansistring;
var     sl      :ansistring;
begin
        if f[i,c]<>'-1' then exit(f[i,c]);
        if i>n then
                if c=0 then
                        begin
                                f[i,c]:='1';
                                exit('1')
                        end
                        else
                        begin
                                f[i,c]:='0';
                                exit('0');
                        end;
        sl:= '0';
                if c0 then
                sl := cong( sl, tinh(i+1,c-1) );
        f[i,c]:=sl;
        exit(sl);
end;
procedure timkq(i,c:longint);
begin
        if i>n then
                begin
                        res:=cong(res,'1');
                        writeln(res);
                        halt;
                end;
        if st[i]='(' then
                begin
                        stack[c+1]:='(';
                        timkq(i+1,c+1);
                end
        else
                if c0 then
                        if stack[c]='(' then
                        res:=cong(res,tinh(i+1,c-1));
                end;
        if st[i]='[' then
                begin
                        stack[c+1]:='[';
                        timkq(i+1,c+1) ;
                end
        else
                if c0 then
                        if stack[c]='[' then
                        res:=cong(res,tinh(i+1,c-1));
                end;
        if st[i]='{' then
                begin
                        stack[c+1]:='{';
                        timkq(i+1,c+1);
                end
        else
                if c0 then
                        if stack[c]='{' then
                        res:=cong(res,tinh(i+1,c-1));
                end;
end;
procedure process;
var     tam:ansistring;
begin
assign(output,fo);rewrite(output);
        tam := tinh(1,0);
        res:='0';
        stack:='';
        timkq(1,0);
close(output);
end;
begin
        enter;
        init;
        process;
end.