1031pa~1.cpp

我的URAL的1000 ~ 1050 的全部代码 包含WA 最后AC的程序 有2~3个比较难的是MAIGO的程序

{time O(n)，较好得利用了决策单调性}
var l1,l2,l3,c1,c2,c3:cardinal;
    dis,f:array[1..10000] of cardinal;
    p1,p2,p3:integer;
    c,d,n:integer;
procedure readin;
  var i,t:integer;
begin
  read(l1,l2,l3,c1,c2,c3);
  read(n,c,d);
  if c>d then begin t:=d; d:=c; c:=t end;
  dis[1]:=0;
  for i:=2 to d do read(dis[i]);
end;

procedure dp;
  var i:integer;
      t:cardinal;
begin
  p1:=c; p2:=c; p3:=c; f[c]:=0;
  for i:=c+1 to d do begin
    f[i]:=maxlongint;

    while (p1<i) and (dis[i]-dis[p1]>l1) do inc(p1);
    if (p1<i) and (c1+f[p1]<f[i]) then f[i]:=c1+f[p1];

    while (p2<i) and (dis[i]-dis[p2]>l2) do inc(p2);
    if (p2<i) and (c2+f[p2]<f[i]) then f[i]:=c2+f[p2];

    while dis[i]-dis[p3]>l3 do inc(p3);
    if c3+f[p3]<f[i] then f[i]:=c3+f[p3];
  end; {for i}
end;{proc dp}

begin
  readin; dp; writeln(f[d]);
end.