POJ 1837(Dp水题)

内容目录

这题居然不用高精度就能过……测试数据好弱

Program P1837;
var
   c,g,i,j,k,p:longint;
   li,w:array[1..20] of longint;
   f:array[1..20,-7500..7500] of longint;
begin
   fillchar(f,sizeof(f),0);
   read(c,g);
   for i:=1 to c do read(li[i]);
   for i:=1 to g do read(w[i]);
   for i:=1 to c do f[1,li[i]*w[1]]:=1;
   for i:=2 to g do
      for j:=1 to c do
      begin
         p:=li[j]*w[i];
         if p<0 then
         begin
            for k:=-7500 to 7500+p do
               if f[i-1,k-p]>0 then
                  inc(f[i,k],f[i-1,k-p])
         end
         else
         begin
            for k:=-7500+p to 7500 do
               if f[i-1,k-p]>0 then
                  inc(f[i,k],f[i-1,k-p]);
         end;
      end;
   writeln(f[g,0]);
end.