比赛 20090916练习赛 评测结果 WWWTTTTTTT
题目名称 任务安排 最终得分 0
用户昵称 ybh 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2009-09-16 22:02:15
显示代码纯文本
program RenWuAnPai;
var
  w,time:array[0..5000] of integer;
  t,f:array[1..5000] of integer;
  kai:array[1..50,1..50] of boolean;
  i,j,j2,n,k,minj:integer;
  min,fhe:longint;
  bool1,bool2:boolean;
begin
  assign(input,'batch.in');
  reset(input);
  assign(output,'batch.out');
  rewrite(output);
  readln(n);
  readln(k);
  for i:=1 to n do
  begin
    readln(t[i],f[i]);
    for j:=1 to n do
      kai[i,j]:=false
  end;
  w[1]:=(k+t[1])*f[1];
  time[1]:=k+t[1];
  kai[1,1]:=true;
  for i:=2 to n do
  begin
    time[i]:=time[i-1]+t[i]+k;
    min:=w[i-1]+time[i]*f[i];
    kai[i]:=kai[i-1];
    bool1:=false;
    bool2:=false;
    for j:=1 to i-1 do
    begin
      fhe:=0;
      for j2:=j to i do
        fhe:=fhe+f[j2];
      if kai[j,j] then
      begin
        if w[j-1]+(time[i]-k)*fhe<min then
        begin
          min:=w[j-1]+time[i]*fhe;
          minj:=j;
          bool1:=true
        end
      end
      else
      begin
        if w[j-1]+time[i]*fhe<min then
        begin
          min:=w[j-1]+time[i]*fhe;
          minj:=j;
          bool2:=true
        end
      end
    end;
    w[i]:=min;
    if bool1
      then time[i]:=time[i]-k
      else if bool2 then
           begin
             time[i]:=time[i];
             kai[i]:=kai[minj];
             kai[i,minj]:=true
           end
           else kai[i,i]:=true;
  end;
  writeln(w[n]);
  close(input);
  close(output);
end.