题目描述

某地铁沿线共设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。

输出

输出文件subway.out只包含一个正整数，表示建成这N个地铁站所需要的最低成本。

思路

我枚举上一次建的位置和上上次建的位置（虽然这没有必要）然后进行dp

var
  f,a:array[-1000..300000,1..3] of int64;
  i,j,k,m,n,x,o,z:longint;
  max:int64;
function min(x,y:longint):longint;
begin
  if x(x,y,z,l:longint):longint;
var
  i:longint;
begin
  if l=1 then x:=maxlongint
    else if l=2 then y:=maxlongint
      else z:=maxlongint;
  i:=min(x,y);
  i:=min(i,z);
  exit(i);
end;
begin
  readln(n);
  for i:=1 to n do
    readln(a[i,1],a[i,2],a[i,3]);
  max:=maxlongint;

  f[1,1]:=a[1,1]; f[1,2]:=a[1,2]; f[1,3]:=a[1,3];
  f[2,1]:=min(a[1,2],a[1,3])+a[2,1];
  f[2,2]:=min(a[1,1],a[1,3])+a[2,2];
  f[2,3]:=min(a[1,2],a[1,1])+a[2,3];

  for i:=3 to n do
  for o:=1 to 3 do
  begin
  f[i,o]:=maxlongint;
    for j:=1 to 3 do
      for k:=1 to 3 do
        if (j<>k) and (o<>j) then
          begin

            f[i,o]:=min(f[i,o],a[i-2,k]+a[i-1,j]+minx(f[i-3,1],f[i-3,2],f[i-3,3],k)+a[i,o]);
          end;
  end;
  for i:=1 to 3 do
    if max>f[n,i] then max:=f[n,i];
  writeln(max);
end.