CHNTOWER - Tháp Hà Nội

Tác giả: ladpro98

Ngôn ngữ: Pascal

program chntower_dp;
uses    math;
const   fi='';
const   a:array[3..64] of int64 =(0,0,12582907,458745,65527,18421,7155,3825,2287,1645,1195,937,743,645,547,465,431,397,363,329,295,285,275,265,255,245,235,225,215,205,195,189,187,185,183,181,179,177,175,173,171,169,167,165,163,
161,159,157,155,153,151,149,147,145,143,141,139,137,135,133,131,129);
var     f:array[0..66,0..66] of qword;
        check:array[0..66,0..66] of boolean;
        m,n:longint;
        inp:text;

procedure init;
var     i:longint;
begin
        fillchar(f,sizeof(f),0);
        fillchar(check,sizeof(check),false);
        for i:=3 to 65 do
        begin
                f[0,i]:=0;
                check[0,i]:=true;
                f[1,i]:=1;
                check[1,i]:=true;
        end;

end;

function dp(n,p:longint):qword;
var     k:longint;
        //res:int64;

begin

        if check[n,p] then exit(f[n,p]);
        f[n,p]:=high(qword);
        if p = 3 then
        begin
                f[n,p]:=2*dp(n-1,3)+1;
                exit(f[n,p]);
                check[n,p]:=true;
        end;
        for k:=0 to n-1 do
        begin
                if f[n,p]>2*dp(k,p)+dp(n-k,p-1)
                then f[n,p]:=2*dp(k,p)+dp(n-k,p-1);

        end;
        //f[n,p]:=res;
        check[n,p]:=true;
        exit(f[n,p]);
end;

begin
        assign(inp,fi);
        reset(inp);
        init;
        while not eof(inp) do
        begin
        readln(inp,n,m);
        {if n = 64 then
        begin
                if m=3 then write('18446744073709551615')
                else if m=4 then write(18433)
                else write(a[m]);
                exit;
        end;  }

        writeln(dp(n,m));
        end;
end.

Download