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.