( 过河问题 ) 在一个月黑风高的夜晚 , 有一群人在

第1题

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

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

#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100;
const int INFINITY = 10000;
const bool LEFT=true;
const bool RIGHT =false; 
const bool LEFT_TO_RIGHT=true;
const bool RIGHT_TO_LEFT=false;
int n,hour[SIZE];
bool pos[SIZE];
int max(int a,int b)
{
 if(a>b)
 return a;
 else
 return b;
} 
int go(bool stage)
{
 int i,j,num,tmp,ans;
 if(stage==RIGHT_TO_LEFT)
 {
 num=0;
 ans=0;
 for(i=1;i<=n;i++)
 if(pos[i]==RIGHT)
 {
 num++;
 if( hour[i]>ans)
 ans=hour[i];
 }
 if( ① ) 
 return ans;
 ans=INFINITY;
 for(i=1;i<=n-1;i++)
 if(pos[i]==RIGHT) 
 for(j=i+1;j<=n;j++)
 if(pos[j]==RIGHT)
 {
 pos[i]=LEFT;
 pos[j]=LEFT;
 tmp=max(hour[i],hour[j])+ ② ;
 if(tmp<ans)
 ans=tmp;
 pos[i]=RIGHT;
 pos[j]=RIGHT;
 }
 return ans;
 }
 if(stage==LEFT_TO_RIGHT)
 {
 ans=INFINITY;
 for(i=1;i<=n;i++)
 if( ③ )
 {
 pos[i]=RIGHT;
 tmp= ④ ;
 if(tmp<ans)
 ans=tmp;
⑤ ;
 }
 return ans;
 }
 return 0;
}
int main() 
{
 int i;
 cin>>n;
 for(i=1;i<=n;i++)
 {
 cin>>hour[i];
 pos[i]=RIGHT;
 }
 cout<<go[RIGHT_TO_LEFT)<<endl;
 return 0;
}