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个地铁站所需要的最低成本。
分析
状态只有三种直接推，这dp要多暴力有多暴力
f[i][j]=min(f[i−1][k]+v[j])(j≠k)
代码
const
maxn=
200100;
var
dp:
array[
0..maxn,
1..
3]
of int64;
note:
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
begin
for j:=
1 to 3 do
read(note[i,j]);
readln;
end;
for i:=
1 to n
do
for j:=
1 to 3 do
dp[i,j]:=maxlongint;
end;
function min(x,y:longint):longint;
begin
if x>y
then exit(y)
else exit(x);
end;
procedure main;
var
i,j,k:longint;
ans:int64;
begin
for i:=
1 to 3 do
dp[
1,i]:=note[
1,i];
for i:=
2 to n
do
for j:=
1 to 3 do
for k:=
1 to 3 do
if j<>k
then dp[i,j]:=min(dp[i,j],dp[i-
1,k]+note[i,j]);
ans:=maxlongint;
for i:=
1 to 3 do
if dp[n,i]<ans
then ans:=dp[n,i];
write(ans);
end;
begin
init;
main;
end.
转载请注明原文地址: https://ju.6miu.com/read-1303809.html
