NOIP 2010 普及组初赛 第28题 过河问题

【题目】

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

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

#include 
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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77

请填空，完善程序。

【题目考点】

1. 深搜

【解题思路】

先看主函数，得知hour[i]表示第i人过河的时长，pos[i]是第i人的位置。看到cout<，可知go函数参数是传入过河的阶段（左到右还是右到左），返回值是所有人从右到左的总时长。
看go函数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];
     }
1
2
3
4
5
6
7
8

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;
            }
1
2
3
4
5
6
7
8
9
10
11
12
13

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;
 }
1
2
3
4
5
6
7
8
9
10
11
12