PersonalCorpus 版 (精华区)

寄信人: No (hi)
标  题: 1167
发信站: 哈工大紫丁香 (2002年03月11日22:05:07 星期一)
来  源: mtlab4.hit.edu.cn 

160218 14:07:10 11 Mar 2002
Bozhang,HIT,P.R.China 1167 Pascal Accepted 0.45 sec 57K

var
    sum:array[0..500,0..1] of word;
    dt:array[1..2,0..500] of integer;
    i,j,k,m,n,t:integer;
begin
    readln(n,k); sum[0,0]:=0;sum[0,1]:=0;
    for i:=1 to n do begin
        readln(j);
        sum[i,1]:=sum[i-1,1]; sum[i,0]:=sum[i-1,0];
        if j=1 then inc(sum[i,1]) else inc(sum[i,0]);
    end;
    fillchar(dt,sizeof(dt),0);
    for m:=1 to n do dt[1,m]:=sum[m,0]*sum[m,1];
    for i:=2 to k do begin
        for m:=i to n do begin
            dt[2,m]:=maxint;
            for j:=i-1 to m-1 do begin
                t:=dt[1,j]+(sum[m,0]-sum[j,0])*(sum[m,1]-sum[j,1]);
                if t<dt[2,m] then dt[2,m]:=t;
            end;
        end;
        for m:=0 to n do dt[1,m]:=dt[2,m];
    end;
    writeln(dt[1,n]);
end.

--
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: mtlab4.hit.edu.cn]
--
※ 转寄:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: mtlab4.hit.edu.cn]