一个旅行家想驾车以最少的费用 PASCAL，问题如下，麻烦重要过程写下讲解。。谢谢

Question

一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。

计算结果四舍五入至小数点后两位。

如果无法到达目的地，则输出“No Solution”。

样例：

INPUT

D1=275.6 C=11.9 D2=27.4 P=2.8 N=2

油站号I
离出发点的距离Di
每升汽油价格Pi

1
102.0
2.9

2
220.0
2.2

OUTPUT

26.95（该数据表示最小费用

Answer 1

分析：需要考虑如下问题：
1） 出发前汽车的油箱是空的，故汽车必须在起点（1号站）处加油。加多少油？
2） 汽车行程到第几站开始加油，加多少油？
可以看出，原问题需要解决的是在哪些油站加油和加多少油的问题。对于某个油站，汽车加油后到达下一加油站，可以归结为原问题的子问题。因此，原问题关键在于如何确定下一个加油站。通过分析，我们可以选择这样的贪心标准：
对于加油站I，下一个加油站J可能第一个是比油站I油价便宜的油站，若不能到达这样的油站，则至少需要到达下一个油站后，继续进行考虑。
对于第一种情况，则油箱需要（d（j）-d（i））/m加仑汽油。对于第二种情况，则需将油箱加满。
贪心算法证明如下：
设定如下变量：
Value[i]：第i个加油站的油价；
Over[i]：在第i站时的剩油；
Way[i]：起点到油站i的距离；
X[I]：X记录问题的最优解，X[I]记录油站I的实际加油量。
首先，X[1]≠0，Over[1]=0。
假设第I站加的X[I]一直开到第K站。则有，X[I]..x[k-1]都为0，而X[K]≠0。
① 若Value[I]>Value[k]，则按贪心方案，第I站应加油为
T=（Way[k]-Way[I]）/M-Over[I]。
若T<X[I]，则汽车无法从起点到达第k个加油站；与假设矛盾。
若T>X[I], 则预示着，汽车开到油站K，仍然有油剩余。假设剩余W加仑汽油，则须费用Value[I]*W，如果W加仑汽油在油站K加，则须费用Value[K]*W，显然Value[K]*W<Value[I]*W。
② 若Value[I]<Value[k]，则按贪心规则，须加油为
T=C-Over[I] （即加满油）。
若T<X[I]，则表示在第I站的加油量会超过汽车的实际载油量，显然是不可能的。
若T>X[I]，则表示在第I站的不加满油，而将一部分油留待第K站加，而Value[I]<Value[k]，所以这样费用更高。

综合上述分析，可以得出如下算法：
I := 1 {汽车出发设定为第1个加油站}
L := C*D2； {油箱装满油能行驶的距离}
repeat
在L距离以内，向后找第一个油价比I站便宜的加油站J；
if J存在 then
if I站剩余油能到达J then
计算到达J站的剩油
else
在I站购买油，使汽车恰好能到达J站
else
在I站加满油；
I := J； {汽车到达J站}
until 汽车到达终点；

程序如下：
program NOI99L_3;
const
Inp = ‘input.txt’;
Outp = ‘output.txt’;
MaxN = 10001; {最大油站数}
Zero = 1e-16; {误差值}
type
Rectype = record {油站的数据结构}
Value: Real; {油价}
Way: Real; {距起点的距离}
Over: Real; {汽车到达该站时的剩油}
end;
RecPtr = ^Rectype; {油站指针}
var
Oil: array [1 .. MaxN] of RecPtr; {记录所有油站}
D1, {起点到终点之间的距离}
C, {汽车油箱的容量}
D2, {每升汽油能行驶的距离}
N: Integer; {油站数}
Cost: Real; {最小油费}
MaxWay, {满油时汽车最大的行驶距离}

function init: Boolean; {初始化，并判无解}
var
I: Integer;
begin
Read (D1, C, D2);
New(Oil[1]); {处理初始值和起始油站}
Oil[1]^.Way := 0;
Read(Oil[1]^.Value,n);
MaxWay := D2 * C;
for I := 2 to n do begin {读入后N-1个油站信息}
New(Oil[I]);
Readln(Oil[I]^.Way, Oil[I]^.Value);
Oil[I]^.over:=0;
end;
Inc(n); {将终点也看成一个加油站}
New(Oil[n]);
Oil[n]^.Way := D1;
Oil[n]^.Value := 0;
Oil[n]^.over:=0;
for I := 2 to n+1 do {判是否无解}
if (Oil[I]^.Way – Oil[I – 1]^.Way > MaxWay) then begin
init:= False;
Exit;
end;
init := True;
end;

procedure Buy(I: Integer; Miles: Real);;
{在I加油站购买Miles/D2加仑汽油}
begin
Cost:= Cost + Miles / D2 * Oil[I]^.Value;
{将买汽油所需的费用加到Cost变量中}
end;

procedure Solve;
var
I, J: Integer;
S: Real;
begin
I := 1; {汽车在起点}
repeat
S := 0.0;
{在MaxWay范围以内，找第一个油价比I站便宜的加油站J}
while (S <= MaxWay+zero) and (J <= N – 1)
and (Oil[I]^.Value <= Oil[J]^.Value) do
begin
Inc(J);
S := S + Oil[J]^.Way – Oil[J – 1]^.Way;
end;
if S <= MaxWay+zero then {如果找到J站或可以直达终点}
{如果剩油足够到达J站，则无需购油，并计算到达J站时汽车的剩油}
if (Oil[I]^.Over + Zero >=Oil[J]^.Way – Oil[I]^.Way) then
Oil[J]^.Over:=Oil[I]^.Over–Oil[J]^.Way+Oil[I]^.Way
else begin
{在I站购买恰好能到达J站的油量}
Buy(I,Oil[J]^.Way – Oil[I]^.Way – Oil[I]^.Over);
Oil[J]^.Over := 0.0;
end
else begin {附近无比I站便宜的加油站J}
Buy(I, MaxWay – Oil[I]^.Over); {在I站加满油}
J := I + 1; {行驶到下一站}
Oil[J]^.Over:= MaxWay – (Oil[J]^.Way – Oil[I]^.Way);
end;
I := J; {汽车直达J站}
until I = N; {汽车到达终点}
end;

begin {主程序}
Cost := 0;
Assign(Input, Inp);
Reset(Input);
Assign(Output, Outp);
Rewrite(Output);
if init then begin {如果有解}
Solve; {求解}
Writeln(Cost:0 :2); {输出最少费用}
end else
Writeln(‘No Solution’); {输出无解}
Close(Input);
Close(Output);
end.追问

问一下你那个误差值是什么意思，为什么会有误差值，而且为什么误差值就是1e-16呢，那个e又是什么

追答

1e-16表示1乘10的负16次方，这表示科学记数法，将误差的范围，缩到这个范围内，可以是任何比较小的数，有的题目会给出。 这个是官方的解答，所以程序相对而言比较具体、全面。我想你应该是今年noip的学生把，我也是的，加油。

Answer 2

program oil;
var
d,c:array[-1..102]of longint;
s,n,v,i,j,max,min,t,x,y:longint;
f:array[-1..100,-1..500]of longint;
function minn(x,y:longint):longint;
begin
if x>y then
x:=y;
minn:=x;
end;
begin
assign(input,'oil.in');
assign(output,'oil.out');
reset(input);
rewrite(output);
readln(s,n,v);
for i:=1 to n do
readln(d[i],c[i]);
max:=0;
for i:=0 to n do
for j:=0 to v do
f[i,j]:=maxlongint;
for i:=d[2] to v do
f[1,i-d[2]]:=i*c[1];
d[n+1]:=s;
for i:=2 to n do//i枚举加油站
for max:=0 to v-d[i]+d[i-1]do
begin
t:=d[i+1]-d[i]-max;
if t<0 then
t:=0;
for j:=t to v-max do
begin
x:=f[i-1,max]+j*c[i];
y:=f[i,j+max-d[i+1]+d[i]];
f[i,j+max-d[i+1]+d[i]]:= minn(x,y);;
end;
end;
min:=maxlongint;
for i:=0 to v do
if min>f[n,i]then
min:=f[n,i];
writeln(min);
close(input);
close(output);
end.

Answer 3

Answer 4