cszqwe 2011-09-09 18:18:00
点我顶贴
收藏
删除
program llx;
var f:array[0..1000,0..1000]of longint;
sum,a,b:array[1..1000]of longint;
ans,i,j,n,m,k,o,p,t:longint;
function max(a,b:ilongint):longint;
begin
if a>b then exit(a) else exit(b);
end;
begin
readln(n,m);
for i:=1 to n do
begin
readln(a[i],b[i]);
if i=1 then sum[i]:=a[i] else sum[i]:=a[i]+sum[i-1];
end;
for i:=1 to n do f[i,0]:=sum[i]*b[1];
for i:=2 to n do
begin
if i-1<m then t:=i-1 else t:=m;
for j:=1 to t do
for k:=j to i-1 do
f[i,j]:=max(f[k,j-1]+(sum[i]-sum[k])*b[k+1],f[i,j]);end;
ans:=0;
for i:=1 to n do if ans<f[i,m]) then ans:=f[i,m];
writeln(ans);
end.