比赛 NOIP2008集训模拟2 评测结果 AAAAAAAAAA
题目名称 阿鲁高的远航 最终得分 100
用户昵称 lc 运行时间 0.000 s
代码语言 Pascal 内存使用 0.00 MiB
提交时间 2008-11-11 11:28:45
显示代码纯文本
program ee3;
 var
     T,V,A,W,i,j,k:longint;
     N,B:array[1..1000] of longint;
     f,g:array[0..1000,0..100] of longint;

procedure print(t,k:longint);
 begin
  if t=0 then exit;
  print(t-1,g[t,k]);
  writeln(k+N[t]-g[t,k]);
 end;



begin
  assign(input,'sail.in');
 assign(output,'sail.out');
 reset(input); rewrite(output);
 readln(T,V,A,W);
 for i:=1 to T do readln(N[i],B[i]);
 fillchar(f,sizeof(f),$FF); f[0,0]:=0;
 for i:=1 to T do
  for j:=0 to V do
   begin
       for k:=0 to V do
         begin
         if (j+N[i]-k>A) or (j+N[i]-k<0) then continue;
         if f[i-1,k]<>-1
         then if
                   (f[i-1,k]+(j+N[i]-k)*B[i]+W*k<f[i,j]) or (f[i,j]=-1)
         then begin
              f[i,j]:=f[i-1,k]+(j+N[i]-k)*B[i]+W*k;
              g[i,j]:=k
              end;
         end;
   end;
 writeln(f[T,0]);
 print(T,0);
 close(input); close(output);
end.