- 货币
- 2015-04-19 21:24:47 @
program exercise(input,output);
type link=^money;
money=record
next:link;
data,num:longint;
end;
var t,n,k:longint;
f:array[0..1000012]of link;
ans:array[0..21]of longint;
function find(x:longint):longint;
var p:link;
begin
if x=0 then
exit(0);
p:=f[x mod 1000013];
while p<>nil do
begin
if p^.num=x then
exit(p^.data);
p:=p^.next;
end;
new(p);
p^.num:=x;
p^.data:=find(x div 2)+find(x div 3)+find(x div 4);
if p^.data<x then
p^.data:=x;
p^.next:=f[x mod 1000013];
f[x mod 1000013]:=p;
exit(p^.data);
p:=nil;
end;
procedure print;
var i:longint;
begin
for i:=1 to t do
writeln(ans[i]);
end;
begin
readln(t);
k:=0;
while k<t do
begin
inc(k);
readln(n);
ans[k]:=find(n);
end;
print;
end.
1 条评论
-
hahayang LV 10 @ 2017-04-30 15:32:44
type thash=^node; node=record p, s:qword; next:thash end; var a:array[1..100017] of thash; n:qword; t, i:longint; function max(a, b:qword):qword; begin if a>b then exit(a) else exit(b) end; function dfs(n:qword):qword; var p1:thash; begin if n=0 then exit(0); p1:=a[n mod 100017]; if p1^.p=n then exit(p1^.s); while p1^.next<>nil do begin p1:=p1^.next; if p1^.p=n then exit(p1^.s) end; new(p1); p1^.p:=n; p1^.s:=max(n, dfs(n div 2)+dfs(n div 3)+dfs(n div 4)); p1^.next:=a[n mod 100017]; a[n mod 100017]:=p1; exit(a[n mod 100017]^.s) end; begin readln(t); for i:=1 to 100017 do begin new(a[i]); a[i]^.p:=0; a[i]^.s:=0; a[i]^.next:=nil end; for i:=1 to t do begin readln(n); writeln(dfs(n)) end; end.
- 1