有n个火车站，从一个站点到另一个站点的费用C与它们的距离L有关，有3种距离，对应有3种费用。现在求从一个站点S到另一个站点E所需的最小费用。
很简单的DP，难度等价于数字三角形，
注意：输入中起点不一定大于终点
View Code
1 program pku2355(input,output); 2 var 3 f :array[0..10010] of longint; 4 d :array[0..10010] of longint; 5 l,c :array[1..3] of longint; 6 x,y :longint; 7 n :longint; 8 procedure swap(var aa,bb:longint); 9 var 10 tt:longint; 11 begin 12 tt:=aa; 13 aa:=bb; 14 bb:=tt; 15 end; 16 procedure init; 17 var 18 i:longint; 19 begin 20 for i:=1 to 3 do 21 read(l[i]); 22 for i:=1 to 3 do 23 read(c[i]); 24 readln; 25 readln(n); 26 readln(x,y); 27 if x>y then 28 swap(x,y); 29 d[1]:=0; 30 for i:=2 to n do 31 readln(d[i]); 32 end; 33 procedure main; 34 var 35 i,j:longint; 36 begin 37 fillchar(f,sizeof(f),63); 38 f[x]:=0; 39 for i:=x+1 to y do 40 begin 41 for j:=i-1 downto x do 42 begin 43 if d[i]-d[j]>l[3] then 44 break; 45 if (d[i]-d[j]<=l[1])and(f[j]+c[1]<f[i]) then 46 f[i]:=f[j]+c[1]; 47 if (d[i]-d[j]<=l[2])and(f[j]+c[2]<f[i]) then 48 f[i]:=f[j]+c[2]; 49 if (d[i]-d[j]<=l[3])and(f[j]+c[3]<f[i]) then 50 f[i]:=f[j]+c[3]; 51 end; 52 end; 53 writeln(f[y]); 54 end; 55 begin 56 init; 57 main; 58 end.
本来这道题O(n^2)算法过不了，但是适当break也水过了，poj马上100道了，等完成最后一道在、再来写线段树优化的程序吧。