题目：
某地铁沿线共设N站，可分为U（地面式）、D（地下式）和C（复合式）三种类型。为避免单调，相邻地铁站的类型不能重复。同时，由于地铁站所处环境和地质条件有所差异，每个站点按不同类型的建设成本也不尽相同。现给定各站点的三种建设成本，请计算出该地铁线的最低总造价。
分析： 这道题 用了DP来解决，用f[i,j]来表示1~i中，第i个地铁站用了第j中模式来建设（1<=j<=3），初始化f[1,j]默认都选了第个模式，然后DP，方程是：
f[i,1]:=min(f[i-1,2],f[i-1,3])+cost[i,1]; f[i,2]:=min(f[i-1,1],f[i-1,3])+cost[i,2]; f[i,3]:=min(f[i-1,1],f[i-1,2])+cost[i,3]; 最后输出f[n,1],f[n,2],f[n,3]之中的最小值。
附上代码： const maxn=200000; var cost,f:array [0..maxn,1..3] of longint; n:longint; procedure init; var i,j,k:longint; begin readln(n); for i:=1 to n do for j:=1 to 3 do read(cost[i,j]); f[1,1]:=cost[1,1]; f[1,2]:=cost[1,2]; f[1,3]:=cost[1,3]; end; function min(a,b:longint):longint; begin if a<b then exit(a); exit(b); end; function min1(a,b,c:longint):longint; begin if a<b then min1:=a else min1:=b; if c<min1 then min1:=c; end; procedure main; var i,j:longint; begin for i:=2 to n do begin f[i,1]:=min(f[i-1,2],f[i-1,3])+cost[i,1]; f[i,2]:=min(f[i-1,1],f[i-1,3])+cost[i,2]; f[i,3]:=min(f[i-1,1],f[i-1,2])+cost[i,3]; end; write(min1(f[n,1],f[n,2],f[n,3])); end; begin init; main; end.
