ac1132.pas

同济大学 Online在线题库 AC源代码合集 程序设计竞赛必看资料

program tju1132;
const
  maxn=100;
  maxmilk=2000;
var
  ok:array[0..maxn shr 1,0..maxmilk shr 1]of boolean;
  a,m:array[0..maxn]of word;
  n,i,j,k,s:word;
function min(a,b:word):word;
  begin
    if a<b then min:=a else min:=b;
  end;
begin
  repeat
    read(n);s:=0;
    for i:=1 to n do begin
      read(a[i]);inc(s,a[i]);
    end;

    fillchar(ok,sizeof(ok),0);ok[0,0]:=true;
    fillchar(m,sizeof(m),0);
    for i:=1 to n do
      for j:=min(i,n shr 1) downto 1 do
        for k:=min(m[j-1]+a[i],s shr 1) downto a[i] do begin
          ok[j,k]:=ok[j,k] or ok[j-1,k-a[i]];
          if ok[j,k] and (k>m[j]) then m[j]:=k;
        end;

    for i:=s shr 1 downto 0 do
      if ok[n shr 1,i] then begin
        writeln(s-i*2);break;
      end;
  until seekeof;
end.