JZOJ8.15（C组）地铁建设

题目：

某地铁沿线共设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     exit(a);
  exit(b);
end;

function min1(a,b,c:longint):longint;
begin
  if a     min1:=a
  else
    min1:=b;
  if c     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.

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！