记录编号	60479	评测结果	AAAAAAAAAAAAAAA
题目名称	钢条切割	最终得分	100
用户昵称	gungnir	是否通过	通过
代码语言	Pascal	运行时间	0.049 s
提交时间	2013-05-25 16:54:23	内存使用	0.19 MiB

var n:integer;
    a,b,f:array[1..2000]of longint;
    num:array[1..2000]of integer;
    i,j,k:integer;

procedure qsort(l,r:integer);
var i,j:integer; temp,mid:longint;
begin
  i:=l; j:=r; mid:=b[(l+r)div 2];

  while i<=j do
  begin
    while (b[i]<mid) do inc(i);
    while (b[j]>mid) do dec(j);
    if (i<=j) then begin temp:=b[i]; b[i]:=b[j]; b[j]:=temp;
                         inc(i); dec(j);
                         end;
  end;
  if (i<r) then qsort(i,r);
  if (l<j) then qsort(l,j);
end;


begin
assign(input,'cutrod.in');reset(input);
assign(output,'cutrod.out');rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);

fillchar(f,sizeof(f),0);

for i:=1 to n do num[i]:=i;

for i:=1 to n do
begin
f[i]:=a[i];
for j:=1 to i do
if (f[i-j]+a[j]>=f[i]) then begin num[i]:=j; f[i]:=f[i-j]+a[j]; end;
end;

writeln(f[n]);
writeln;
i:=n;k:=0;
while (num[i]<>i)do
begin
j:=num[i];
i:=i-j;
k:=k+1; b[k]:=j;
end;

k:=k+1; b[k]:=i;

qsort(1,k);

for i:=k downto 1 do write(b[i],' ');
close(input); close(output);
end.