（NOIP2010）过河问题

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

#include<iostream>
#include<string>
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){
    return a>b?a: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;
}

①处应填（ ）。
{{ select(1) }}

• num<=0
• num<=1
• num<=2
• num<=3

②处应填（ ）。
{{ select(2) }}

• go(LEFT)
• go(RIGHT)
• go(LEFT_TO_RIGHT)
• go(RIGHT_TO_LEFT)

③处应填（ ）。
{{ select(3) }}

• pos[i]==LEFT
• pos[i]==RIGHT
• pos[i]==LEFT_TO_RIGHT
• pos[i]==RIGHT_TO_LEFT

④处应填（ ）。
{{ select(4) }}

• hour[i]+go(RIGHT_TO_LEFT)
• hour[i]-go(RIGHT_TO_LEFT)
• hour[i]+go(LEFT_TO_RIGHT)
• hour[i]-go(LEFT_TO_RIGHT)

⑤处应填（ ）。
{{ select(5) }}

• pos[i]=LEFT
• pos[i]=RIGHT
• pos[i]=LEFT_TO_RIGHT
• pos[i]=RIGHT_TO_LEFT