> program p_1011;
> const
>   maxn=10000;
>   var
>     f,a:array[0..maxn] of longint;
>     n,sum:longint;
>     
>  procedure main;
>    var i,j,ans:longint;
>    begin
>      sum:=0;
>      for i:=1 to n do
>          begin
>               read(a[i]);
>               inc(sum,a[i]);
>          end;
>      fillchar(f,sizeof(f),0);
>      f[0]:=1;
>      for i:=n downto 1 do
>          for j:=sum downto a[i] do
>                     inc(f[j],f[j-a[i]]);
>      {for i:=1 to sum do write(f[i],' ');
>      writeln;}
>      ans:=maxlongint;
>      for j:=1 to sum do
>          if f[j]<>0 then
>            if sum mod f[j]=0 then
>                    if sum div f[j]<ans then ans:=sum div f[j];
>      writeln(ans);
>    end;
> 
>  begin
>    assign(input,'p_1011.in');
>    reset(input);
>    assign(output,'p_1011.out');
>    rewrite(output);
>      readln(n);
>      while n<>0 do begin main;readln(n);end;
>    close(input);
>    close(output);
>  end.
{思路是先把能组合的方案求出来，定义f[i]为能组合出i的方案的种数，
ans=min(sum div f[i]);
}

• Re:这道题应该是搜+剪枝的吧。 (70) schindlerlee 2010-01-10 16:20:24