(过河问题) 在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到河的左岸.在伸手不见五指的黑夜里,过桥时必须借照灯光来照明,不幸的是,他们只有一盏灯.另外,独木桥上最多能承受两个人同时经过,否则将会坍塌.每个人单独过独木桥都需要一定的时间,不同的人要的时间可能不同.两个人一起过独木桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥所花费的时间.现在输入N(2<=N<1000)和这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_LEFT)
     then begin
        num := 0;
        ans :=0;
        for i := 1 to n do 
           if pos[i] = Rignt 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;
end
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.