（过河问题） 在一个月黑风高的夜晚，有一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸。在伸手不见五指的黑夜里，过桥时必须借照灯光来照明，不幸的是，他们只有一盏灯。另外，独木桥上最多能承受两个人同时经过，否则将会坍塌。每个人单独过独木桥都需要一定的时间，不同的人要的时间可能不同。两个人一起过独木桥时，由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥所花费的时间。现在输入 $N(2\leq N<1000)$ 和这 $N$ 个人单独过桥需要的时间,请计算总共最少需要多少时间,他们才能全部到达河左岸。

例如，有 $3$ 个人甲、乙、丙，他们单独过桥的时间分别为 $1,2,4$，则总共最少需要的时间为 $7$。具体方法是：甲、乙一起过桥到河的左岸，甲单独回到河的右岸将灯带回，然后甲、丙在一起过桥到河的左岸，总时间为 $2+1+4=7$。

1#include<iostream>2#include<cstring>3using namespace std;4const int SIZE=100;5const int INFINITY = 10000;6const bool LEFT=true;7const bool RIGHT =false;8const bool LEFT_TO_RIGHT=true;9const bool RIGHT_TO_LEFT=false;10 11int n,hour[SIZE];12bool pos[SIZE];13 14int max(int a,int b)15{16    if(a>b)17       return a;18    else19       return b;20}21int go(bool stage)22{23    int i,j,num,tmp,ans;24    if(stage==RIGHT_TO_LEFT)25    {26        num=0;27        ans=0;28        for(i=1;i<=n;i++)29           if(pos[i]==RIGHT)30           {31               num++;32               if( hour[i]>ans)33                   ans=hour[i];34           }35        if(         ①        )36            return ans;37        ans=INFINITY;38        for(i=1;i<=n-1;i++)39           if(pos[i]==RIGHT)40               for(j=i+1;j<=n;j++)41                  if(pos[j]==RIGHT)42                  {43                      pos[i]=LEFT;44                      pos[j]=LEFT;45                      tmp=max(hour[i],hour[j])+         ②       ;46                      if(tmp<ans)47                         ans=tmp;48                      pos[i]=RIGHT;49                      pos[j]=RIGHT;50 51                  }52        return ans;53    }54    if(stage==LEFT_TO_RIGHT)55    {56        ans=INFINITY;57        for(i=1;i<=n;i++)58            if(         ③        )59            {60                pos[i]=RIGHT;61                tmp=        ④         ;62                if(tmp<ans)63                    ans=tmp;64                        ⑤      ;65            }66        return ans;67    }68    return 0;69}70 71int main()72{73    int i;74    cin>>n;75    for(i=1;i<=n;i++)76    {77        cin>>hour[i];78        pos[i]=RIGHT;79    }80    cout<<go[RIGHT_TO_LEFT)<<endl;81    return 0;82}