/ Vijos / 讨论 / 货币 /

为什么只过一组?(pascal)

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 条评论

  • @ 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

信息

ID
1599
难度
7
分类
搜索 | 记忆化搜索 点击显示
标签
(无)
递交数
2481
已通过
414
通过率
17%
被复制
4
上传者