Description
某地铁沿线共设N站，可分为U（地面式）、D（地下式）和C（复合式）三种类型。为避免单调，相邻地铁站的类型不能重复。同时，由于地铁站所处环境和地质条件有所差异，每个站点按不同类型的建设成本也不尽相同。现给定各站点的三种建设成本，请计算出该地铁线的最低总造价。
输入文件subway.in包含N+1行： 第1行为一个正整数，表示地铁站的总数N。 第2行到第N+1行分别包含用空格分隔的三个正整数U，D和C。其中第i+1行表示第i个地铁站按U、D 或C 类型的建设成本，1≤i≤N。
Output
输出文件subway.out只包含一个正整数，表示建成这N个地铁站所需要的最低成本。
3
1 99 99
99 1 99
99 99 1
Sample Output
3
对于20%的数据，N≤10； 对于40%的数据，N≤1000； 对于100%的数据，N≤200000，1≤U, D, C≤10000。
题解
dp，f[i,j]表示第i个地铁站选择j种方案，但我们可以发现j最大为3，而且可以枚举，所以...
f[i,1]:=f[i,1]+min(f[i-1,2],f[i-1,3])
f[i,2]:=f[i,2]+min(f[i-1,1],f[i-1,3])
f[i,3]:=f[i,3]+min(f[i-1,2],f[i-1,1])
代码
var
a:
array[
0..
300000,
1..
3]
of longint;
n,i,ans:longint;
function min(x,y:longint):longint;
begin
if x<y
then exit(x)
else exit(y);
end;
begin
readln(n);
for i:=
1 to n
do
readln(a[i,
1],a[i,
2],a[i,
3]);
for i:=
1 to n
do
begin
a[i,
1]:=a[i,
1]+min(a[i-
1,
2],a[i-
1,
3]);
a[i,
2]:=a[i,
2]+min(a[i-
1,
1],a[i-
1,
3]);
a[i,
3]:=a[i,
3]+min(a[i-
1,
1],a[i-
1,
2]);
end;
ans:=min(a[n,
1],a[n,
2]);
ans:=min(ans,a[n,
3]);
writeln(ans);
end.
转载请注明原文地址: https://ju.6miu.com/read-1305507.html
