URAL/1031

来自"NOCOW"

首先这道题O(n^2)的Dp可以过，但仍然有O(N)的DP，先讲n^2的f[i]=f[j]+work(i,j) 其中j<i,且i，j可达，f[i]表示到i站所需的钱，work(i,j)表示对应的车票价格。

那么下面来看看线性算法，首先题目的条件保证了f为不递减的，所以每次跟新的时候不用所有的j去更新，只需要在L1范围内最远的点，在L2范围内最远的点，在L3范围内最远的点，这三个点去更新即可。

这里只给出了n^2的Dp

program cao;
const
  maxn=11000;
 
var
  f,data:array[0..maxn] of longint;
  a,b,c,d,e,g,h,i,j,k,l,n,m,p,q,l1,l2,l3,c1,c2,c3,s,t:longint;
 
function min(a,b:longint):longint;
begin
  if a>b then exit(b) else exit(a);
end;
 
procedure init;
begin
  read(l1,l2,l3,c1,c2,c3,n,s,t);
  for i:=2 to n do
    read(data[i]);
end;
 
procedure main;
begin
  if s>t then
  begin
    a:=s;
    s:=t;
    t:=a;
  end;
  for i:=s+1 to t do
  begin
    f[i]:=maxlongint;
    for j:=i-1 downto s do
    begin
      d:=data[i]-data[j];
      if d<=l1 then f[i]:=min(f[i],f[j]+c1)
      else
      if d<=l2 then f[i]:=min(f[i],f[j]+c2)
      else
      if d<=l3 then f[i]:=min(f[i],f[j]+c3)
      else
      break;
    end;
  end;
end;
 
procedure print;
begin
  writeln(f[t]);
end;
 
begin
  init;
  main;
  print;
end.

http://withflying.com/?p=79

http://withflying.com