NOIP2010年第十六届普及组初赛完善程序题:(过河问题)在一个月黑风高的夜晚,有一群人在河的右岸,想通过唯一的一根独木桥走到河的左岸。在这伸手不见五指的黑夜里,过桥时必须借助灯光来照明,很不幸的是,他们只有一盏灯。另外,独木桥上最多承受两个人同时经过,否则将会坍塌。每个人单独过桥都需要一定的时间,不同的人需要的时间可能不同。两个人一起过桥时,由于只有一盏灯,所以需要的时间是较慢的那个人单独过桥时所花的时间。现输入n(2≤n<100)和这n个人单独过桥时需要的时间,请计算总共最少需要多少时间,他们才能全部到达河的左岸。 例如,有3个人甲、乙、丙,他们单独过桥的时间分别为1、2、4,则总共最少需要的时间为7。具体方法是:甲、乙一起过桥到河的左岸,甲单独回到河的右岸将灯带回,然后甲、丙再一起过桥到河的左岸,总时间为2+1+4=7。
#include <iostream> usingnamespacestd; constint SIZE = 100; constint INFINITY = 10000; constbool LEFT = true; constbool RIGHT = false; constbool LEFT_TO_RIGHT = true; constbool 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; }