过桥问题：1、2、5、10 分钟

题

夜里 4 个人要过一座桥，单程各需 1、2、5、10 分钟。桥一次最多走两人，只有一个手电筒，过桥必须打着手电，两人同行按慢者速度。手电不能扔，只能有人拿回来。最少多少分钟全部过桥？

一句话

17 分钟——关键一步是让 5 和 10 同行，两个最慢的人共用一次 10 分钟；直觉上的"最快者来回护送"要 19 分钟。

关键技巧

手电每次过去两人、回来一人，所以 \(n\) 人需要 \(n-1\) 次去、\(n-2\) 次回。能优化的只有两件事——慢的人尽量搭伙过，回程尽量由快的人跑。

把人按速度排好 \(a \le b \le \cdots \le c \le d\)，每一轮只处理当前最慢的两人 \(c, d\)，两种送法：

• 策略 A：\(a\) 护送。\(a\) 带 \(d\) 过去、\(a\) 回来；\(a\) 带 \(c\) 过去、\(a\) 回来。耗时 \(d + a + c + a = 2a + c + d\)。
• 策略 B：慢者同行。\(a, b\) 过去、\(a\) 回来；\(c, d\) 过去、\(b\) 回来。耗时 \(b + a + d + b = a + 2b + d\)。

两式都有 \(a + d\)，差别只剩

\(2b < a + c\) 时选 B，否则选 A。 B 付出的代价是 \(b\) 多跑两趟，换来的是 \(c\) 不用单独过桥、\(a\) 少回一趟。

每轮送走两人后，剩下的还是同一结构的子问题。于是有两行 DP（\(f(k)\) 表示最快的 \(k\) 人全部过桥的最少时间，\(t_1 \le \cdots \le t_n\)）：

第一项是 A 的单步版本（\(t_1\) 送走 \(t_k\) 再回来），第二项是 B。这条 DP 在 \(n \le 7\) 的随机实例上与 Dijkstra 全状态穷举逐一吻合（见折叠块）。

解

\(a, b, c, d = 1, 2, 5, 10\)：\(2b = 4 < a + c = 6\)，选 B。

对照策略 A：\(10 + 1 + 5 + 1 + 2 = 19\)。差的 2 分钟恰好是 \((a + c) - 2b = 6 - 4\)。

17 为什么不能再少：4 人要 3 次去、2 次回，3 次去程共得运过 \(4 + 2 = 6\) 人次，所以每次去程都是两人。若 5 和 10 分在两趟，这两趟就是 15，第三趟去程至少 2，两次回程至少各 1，合计 \(\ge 19\)。所以两人必须同行。这一趟不可能是第一趟（之后得有 5 或 10 回程），也不可能是最后一趟（前两趟去程里 5、10 必有一人出场）——只能在中间，对岸得事先有个快的人等着把手电拿回来，这就逼出了第 1、2 步。

延伸

• 切换条件因人而异：\(1, 4, 5, 10\) 时 \(2b = 8 > a + c = 6\)，改用 A，答案 \(10 + 1 + 5 + 1 + 4 = 21\)。\(1, 2, 3, 4\) 时 \(4 = 4\)，两种一样，答案 11。
• \(n\) 人贪心：从最慢的两人开始，每轮按 \(2b\) 与 \(a + c\) 比较选 A 或 B，剩 3 人时 \(a+b+c\)，剩 2 人时 \(b\)。由于 \(c\) 越往后越小，一旦某轮选了 A，之后全是 A——最优方案是"先若干轮 B，再若干轮 A"。例：\(1, 2, 5, 10, 12, 20\) 两轮都选 B，得 \(25 + 15 + 2 = 42\)。
• 常见错误一：以为最快的人每趟都陪着最省。只在 \(b\) 相对 \(a, c\) 很慢时成立。
• 常见错误二：让慢的人回程。回程只该由最快的 \(a\) 或 \(b\) 跑——DP 的两种动作正是这样搭的，Rote（2002）给出了这条 DP 最优性的完整证明，下方穷举在小规模上复核。
• 桥容量 \(k > 2\)：结构变了，每趟去 \(k\) 人回 1 人，最优分组不再是简单的"两慢同行"，得靠 DP 或整数规划。有兴趣可以把下方 Dijkstra 的 (1, 2) 换成 range(1, k+1) 直接跑。
• 同类技巧：只看"最慢两人怎么送"的局部交换论证，和两个鸡蛋的 DP 一样，都是把大问题剥成同构子问题。

import heapq, random, itertools

def brute(ts):
    """状态 = (对岸集合 bitmask, 手电在哪岸)。每次过 1 或 2 人。"""
    n, full = len(ts), (1 << len(ts)) - 1
    dist, pq = {(0, 0): 0}, [(0, 0, 0)]
    while pq:
        d, far, side = heapq.heappop(pq)
        if far == full:
            return d
        if d > dist[(far, side)]:
            continue
        here = [i for i in range(n) if ((far >> i) & 1) == side]
        for k in (1, 2):
            for g in itertools.combinations(here, k):
                m = sum(1 << i for i in g)
                nf = far | m if side == 0 else far & ~m
                nd = d + max(ts[i] for i in g)
                if nd < dist.get((nf, 1 - side), 1e18):
                    dist[(nf, 1 - side)] = nd
                    heapq.heappush(pq, (nd, nf, 1 - side))

def dp(ts):
    t = sorted(ts); n = len(t)
    if n == 1:
        return t[0]
    f = [0] * (n + 1)
    f[1], f[2] = t[0], t[1]
    for k in range(3, n + 1):
        f[k] = min(f[k - 1] + t[0] + t[k - 1],             # 最快者护送最慢者
                   f[k - 2] + t[0] + 2 * t[1] + t[k - 1])   # 最慢两人同行
    return f[n]

print(brute([1, 2, 5, 10]), dp([1, 2, 5, 10]))   # 17 17
random.seed(4)
for _ in range(500):
    ts = [random.randint(1, 20) for _ in range(random.randint(1, 7))]
    assert brute(ts) == dp(ts), ts
print("n<=7 随机 500 组：DP == 穷举")
for ts in ([1, 4, 5, 10], [1, 2, 3, 4], [1, 2, 5, 10, 12, 20]):
    print(ts, dp(ts), brute(ts))
# [1, 4, 5, 10] 21 21
# [1, 2, 3, 4] 11 11
# [1, 2, 5, 10, 12, 20] 42 42