trip.pas

PASCAL光盘资料PASCAL光盘资料PASCAL光盘资料

program trip(input,output);
const max=1000;
var i,n:longint;
    c,d2:real;
p,d,consume:array[0..max] of real;

function minp(b,e:longint):longint;{在b站到e站之间从后往前找油价最低的站}
var i,k:longint;
    tempminp:real;
begin
     tempminp:=p[e]; k:=e;
     for i:=e-1 downto b do
         if p[i]<tempminp then
           begin tempminp:=p[i]; k:=i end;
     minp:=k
end;

function money(start,stop:longint;rest:real):real;
var k:longint;
begin
  if stop-start=1
then money:=((d[stop]-d[start])/d2-rest)*p[start]
     else begin
            k:=minp(start,stop-1);
            if k<>start{油价最低的加油站不是起点站}
              then money:=money(start,k,rest)+money(k,stop,0)
              else if d[stop]-d[start]<=d2*c{在起点加满油能直接到达该段终点}
                     then money:=((d[stop]-d[start])/d2-rest)*p[start]
                     else begin
                            k:=minp(start+1,stop-1);
                          if d[k]-d[start]<=d2*c
then{在起点加满油能到达加油站k}
money:=(c-rest)*p[start]+money(k,stop,c-(d[k]-d[start])/d2)
{在起点处加满油箱共加油c-rest升，到达加油站k用去(d[k]-d[start])/d2}
else money:=money(start,k,rest)+money(k,stop,0)
                          end
          end
end;

begin {main}
  assign(input,'trip.in');
  assign(output,'trip.out');
  reset(input);
  rewrite(output);
  readln(d[0],c,d2,p[0],n);
  d[n+1]:=d[0];
  for i:=1 to n do  readln(d[i],p[i]);
  d[0]:=0;
  for i:=n downto 0 do consume[i]:=(d[i+1]-d[i])/d2;
  for i:=0 to n do
    if consume[i]>c then
     begin writeln('No Solution'); close(output);halt end;
  writeln(money(0,n+1,0):0:2);  {起点站编号为0，终点站编号为n+1}
  close(input);
  close(output)
end.