NOIP 2010 普及组初赛试题完善程序4.2（过河问题）
在一个月黑风高的夜晚，
有一群人在河的右岸，想通过唯一的一根独木桥走到河的左岸。
在这伸手不见五指的黑夜里，
过桥时必须借助灯光来照明，
很不幸的是，他们只有一盏灯。
另外，独木桥上最多承受两个人同时经过，
否则将会坍塌。每个人单独过桥都需要一定的时间，
不同的人需要的时间可能不同。
两个人一起过桥时，
由于只有一盏灯，所以需要的时间是较慢的那个人单独过桥时所花的时间。
现输入n（2≤n<100）和这n个人单独过桥时需要的时间，
请计算总共最少需要多少时间，他们才能全部到达河的左岸。
例如，有3个人甲、乙、丙，他们单独过桥的时间分别为1、2、4，
则总共最少需要的时间为7。
具体方法是：
甲、乙一起过桥到河的左岸，
甲单独回到河的右岸将灯带回，然后甲、丙再一起过桥到河的左岸，
总时间为2+1+4=7。
#include <iostream>
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)//const bool RIGHT_TO_LEFT = false;
{
int i, j, num, tmp, ans;
if (stage == RIGHT_TO_LEFT) //false
{
num = 0;
ans = 0;
for (i = 1; i <= n; i++) //false
{
if (pos[i] == RIGHT)
{
num++;
if (hour[i] > ans)
ans = hour[i];
}
}
if ([ ① ]) //num<=2 特判
return ans;
//const int INFINITY = 10000;
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]) +[ ② ];//go(LEFT_TO_RIGHT)
if (tmp < ans)
ans = tmp;
//pos 这个人在左岸还是右岸
pos[i] = RIGHT;
pos[j] = RIGHT;
}
}
return ans;
}
//stage 当前的状态
if (stage == LEFT_TO_RIGHT)
{
ans = INFINITY;//ans=10000;
for (i = 1; i <= n; i++)
{
if ([ ③ ]) //pos[i] == LEFT;
{
pos[i] = RIGHT;
tmp =[ ④ ]; //hour[i]+go(RIGHT_TO_LEFT)
if (tmp < ans)
ans = tmp;
[ ⑤ ];//pos[i] = LEFT;
}
}
return ans;
}
return 0;
}
int main()
{
int i;
cin>>n;
for (i = 1; i <=n; i++)
{
cin>>hour[i];
pos[i] = RIGHT;
}
/*
const bool LEFT = true;
const bool RIGHT = false;
const bool LEFT_TO_RIGHT = true;
const bool RIGHT_TO_LEFT = false;
*/
cout<<go(RIGHT_TO_LEFT)<<endl;
return 0;
}
/*
1.正确答案： num <= 2 / num < 3|num == 2
2.正确答案： go(LEFT_TO_RIGHT)
3.正确答案： pos[i] == LEFT / LEFT == pos[i]
4.正确答案： hour[i] + go(RIGHT_TO_LEFT) / go(RIGHT_TO_LEFT) + hour[i]
5.正确答案： pos[i] = LEFT
*/
