CODEVS2144 砝码称重2 (哈希表)

由于m很大，所以不能使用DP。

注意到n≤30，直接暴力2^n会TLE。

所以，将砝码平均分成两份，对一份进行一次暴力，用哈希表存下可能的结果。

对下一份再进行一次暴力，在哈希表中搜索剩余的砝码重量是否存在，若存在则更新答案。

输出最小答案即可。

Program CODEVS2144;
const maxn=100;
      maxh=100007;
var a:array[0..maxn] of longint;
    n,i,ans:longint;
    m:int64;
    h:array[0..maxh,1..2] of longint;
procedure insert(x,y:longint);
var hash:longint;
begin
  hash:=x mod maxh;
  while (h[hash,1]<>-1) and (h[hash,1]<>x) do
    hash:=(hash+1) mod maxh;
  if h[hash,1]=-1 then
    begin
      h[hash,1]:=x;
      h[hash,2]:=y;
    end
  else
    if y<h[hash,2] then h[hash,2]:=y;
end;
function find(x:longint):longint;
var hash:longint;
begin
  hash:=x mod maxh;
  while (h[hash,1]<>-1) and (h[hash,1]<>x) do
    hash:=(hash+1) mod maxh;
  if h[hash,1]=-1 then exit(0) else
    exit(h[hash,2]);
end;
procedure dfs(x:longint;sum:int64;num:longint);
begin
  if sum>m then exit;
  if x=n div 2+1 then
    begin
       insert(sum,num);
       exit;
    end;
  dfs(x+1,sum,num);
  dfs(x+1,sum+a[x],num+1);
end;
procedure work(x:longint;sum:int64;num:longint);
var j:longint;
begin
  if sum>m then exit;
  if x=n+1 then
    begin
           if sum=m then
             begin
                   if num<ans then ans:=num;
                   exit;
             end;
       j:=find(m-sum);
       if j<>0 then
         begin
           if j+num<ans then
             ans:=j+num;
         end;
       exit;
    end;
  work(x+1,sum,num);
  work(x+1,sum+a[x],num+1);
end;
begin
  for i:=1 to maxh do h[i,1]:=-1;
  readln(n,m);
  for i:=1 to n do readln(a[i]);
  ans:=maxn;
  dfs(1,0,0);
  work(n div 2+1,0,0);
  writeln(ans);
end.

CODEVS2144 砝码称重2 (哈希表)

相关推荐