不是VIP会员,不能显示答案

题目解答

题目:
(过河问题)在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走
到河的左岸。在这伸手不见五指的黑夜里,过桥时必须借助灯光来照明,不幸的是,他们只有一盏灯。另外,独木桥上最多承受两个人同时经过,否则将会坍塌。每个人单独过桥都需要一定的时间,不同的人需要的时间可能不同。两个人一起过桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入n(2<=n<100)和这n个人单独过桥时需要的时间,请计算总共最少需要多少时间,他们才能全部到达河的左岸。
例如,有3个人甲、乙、丙,他们单独过桥的时间分别为1、2、4则总共最少需要的时间为7。具体方法是:甲、乙一起过桥到河的左岸,甲单独回到河的右岸将灯带回,然后甲、丙再一起过桥到河的左岸,总时间为2+1+4=7。
const
  size=100;
  infinity=10000;
  left=true;
  right=false;
  left_to_right=true;  
  right_to_left=false;
var
  n,i:integer;
  time:array [1..size] of integer;
  pos:array [1..size] of boolean;
function max(a,b:integer):integer;
begin
  if a>b then
max:=a
  else
max:=b;
end;
function go(stage:boolean):integer;
var
  I,j,num,tmp,ans:integer;
begin
  if (stage=right_to_lefft) then
begin
   num:=0;
   ans:=0;
   for i:=1 to n do
     if pos[i]=right then  
       begin
         inc(num);
         if time[i]>ans then
           ans:=time[i];
       end;
    if      num<=2        then
       begin
          go:=ans;
          exit;
       end;
    ans:=infinity;
    for i:=1 to n-1 do
       if pos[i]=right then
          for j:=i+1 to n do
            if pos[j]=right then
               begin
                    pos[i]:=left;
                    pos[j]:=left;
                    tmp:=max(time[i],time[j])+       go(LEFT_TO_RIGHT)       ;
                    if tmp<ans then
                        ans:=tmp;
                    pos[i]:=right;  
                    pos[j]:=right;
               end;
      go:=ans;
  else
     if (stage=left_to_right) then
       begin
         ans:=infinity;
         for i:=1 to n do
           if       pos[i]=LEFT           then
              begin
                pos[i]:=right;
                tmp:=         time[i]+go(RIGHT_TO_LEFT)          ;
                if tmp<ans then
                  ans:=tmp;
                           pos[i]:= LEFT              ;
               end;
         go:=ans;
end
else
  go:=0;
  end;
begin  
  readln(n);
  for i:=1 to n do
begin
   read(time[i]);
   pos[i]:=right;
end;
  writeln(go(right_to_left));
end. 
考点:
分析:
解答:
评论:
老师: