Az alábbi letöltési lehetőségek közül választhatsz: (
segítség)
Típus: text/plain
Tartalmaz szöveget
Karakterkódolás: us-ascii
Méret: 1 KB
program malom;
type mal=record
kit :longint;
tav :longint;
end;
cella=record
ut :longint;
ar :longint;
end;
var n,k :longint;
a :array[0..101] of mal;
b :array[0..101,0..101] of cella;
s :array[0..101] of longint;
r :array[0..101] of longint;
procedure beolvas;
var i :longint;
t :text;
begin
assign(t,'malom.be');
reset(t);
readln(t,n,k);
for i:=1 to n do
begin
a[i].kit:=0;
a[i].tav:=0;
end;
for i:=1 to n do
begin
readln(t,a[i].tav,a[i].kit);
end;
close(t);
end;
function szakasz(e,f :longint) :longint;
begin
szakasz:=s[f-1]-s[e]-(r[f-1]-r[e])*a[e].tav;
end;
procedure kitolt;
var i,j,min,l,minut,x,y :longint;
begin
for i:=0 to 101 do
begin
for j:=0 to 101 do
begin
b[i,j].ut:=0;
b[i,j].ar:=0;
end;
end;
for i:=0 to 101 do
begin
s[i]:=0;
r[i]:=0;
end;
for i:=1 to n do
begin
s[i]:=s[i-1]+a[i].kit*a[i].tav;
r[i]:=r[i-1]+a[i].kit;
end;
for i:=0 to n do
begin
b[0,i].ar:=s[i];
b[0,i].ut:=i;
end;
for i:=1 to k do
begin
for j:=i to n do
begin
min:=s[n];
minut:=n;
for l:=i to j do
begin
if b[i-1,l-1].ar+szakasz(l,j+1)<min then
begin
min:=b[i-1,l-1].ar+szakasz(l,j+1);
minut:=l;
end;
end;
b[i,j].ar:=min;
b[i,j].ut:=minut;
end;
end;
writeln(b[k,n].ar);
x:=k;
y:=n;
for i:=1 to k do
begin
writeln(b[x,y].ut);
x:=x-1;
y:=b[x,y].ut-1;
end;
end;
begin
beolvas;
kitolt;
end.
