地鐵建設 (Standard IO)

Description

某地鐵沿線共設N站，可分為U（地面式）、D（地下式）和C（複合式）三種類型。為避免單調，相鄰地鐵站的類型不能重複。同時，由于地鐵站所處環境和地質條件有所差異，每個站點按不同類型的建設成本也不盡相同。現給定各站點的三種建設成本，請計算出該地鐵線的最低總造價。

Input

輸入檔案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嘛。

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]);

代碼

var
  a:array[..,..] 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:= to n do
    readln(a[i,],a[i,],a[i,]);
  for i:= to n do
    begin
      a[i,]:=a[i,]+min(a[i-,],a[i-,]);
      a[i,]:=a[i,]+min(a[i-,],a[i-,]);
      a[i,]:=a[i,]+min(a[i-,],a[i-,]);
    end;
  ans:=min(a[n,],a[n,]);
  ans:=min(ans,a[n,]);
  writeln(ans);
end.


var
  a:array[..,..] 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:= to n do
    readln(a[i,],a[i,],a[i,]);
  for i:= to n do
    begin
      a[i,]:=a[i,]+min(a[i-,],a[i-,]);
      a[i,]:=a[i,]+min(a[i-,],a[i-,]);
      a[i,]:=a[i,]+min(a[i-,],a[i-,]);
    end;
  ans:=min(a[n,],a[n,]);
  ans:=min(ans,a[n,]);
  writeln(ans);
end.