USACO 2018 Balance Beam 详细题解

问题描述与分析

Bessie 在平衡木上表演，平衡木上的位置标记为 $0, 1, \ldots, N+1$。在每个位置 $k$，她面临两个选择：

1. 跳下平衡木：获得确定的报酬 $f(k)$
2. 继续移动：投掷硬币，以 $\frac{1}{2}$ 的概率移动到 $k-1$，以 $\frac{1}{2}$ 的概率移动到 $k+1$

如果 Bessie 到达位置 $0$ 或 $N+1$，她会掉下去且得不到任何报酬。

目标：对于每个起始位置 $i$ ($1 \leq i \leq N$)，求出在最优策略下的期望报酬，并将该期望值乘以 $10^5$ 后向下取整输出。

数学建模与关键洞察

1. 期望方程建立

设 $E[i]$ 表示从位置 $i$ 出发采用最优策略所能获得的期望报酬。根据题意，我们可以写出递推关系：

$$E[i] = \max\left(f(i), \frac{E[i-1] + E[i+1]}{2}\right) $$

边界条件：

$$E[0] = E[N+1] = 0$$

这个方程的含义很直观：

• 如果直接跳下获得的报酬 $f(i)$ 高于继续移动的期望报酬，那么最优选择是直接跳下
• 否则，应该继续移动，期望报酬是左右相邻位置期望报酬的平均值

2. 凸包性质的发现

这个问题的关键在于发现：最优解序列 $E[0], E[1], \ldots, E[N+1]$ 构成了原序列 $f(0), f(1), \ldots, f(N+1)$ 的上凸包。

为什么是凸包？

考虑三个连续的位置 $i-1, i, i+1$：

• 如果 $E[i] > \frac{E[i-1] + E[i+1]}{2}$，说明点 $(i, E[i])$ 在连接 $(i-1, E[i-1])$ 和 $(i+1, E[i+1])$ 的线段之上
• 如果 $E[i] = \frac{E[i-1] + E[i+1]}{2}$，说明点 $(i, E[i])$ 正好在线段上

这正好符合上凸包的定义：所有点都在连接任意两点的线段之下或在线段上。

3. 凸包判断条件

对于三个点 $A = (x_a, y_a)$, $B = (x_b, y_b)$, $C = (x_c, y_c)$，判断 $B$ 是否在 $AC$ 线段下方（即是否应该被移除出凸包）的条件是：

$$(y_c - y_b) \times (x_b - x_a) > (y_b - y_a) \times (x_c - x_b) $$

这个不等式来源于向量叉积的几何意义，判断点 $B$ 相对于线段 $AC$ 的位置。

算法设计与实现

1. 整体算法流程

1. 预处理：读入数据并将 $f(i)$ 乘以 $10^5$，设置边界值
2. 构建凸包：使用单调栈算法计算上凸包
3. 计算答案：对于每个位置，如果在凸包顶点上则直接输出，否则线性插值

2. 详细代码解析

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 1e5 + 10;

int n;
ll v[maxn];      // 存储f(i) * 1e5
int st[maxn], tp; // 单调栈，存储凸包顶点下标

int main() {
    // 读入数据
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &v[i]);
        v[i] *= 100000; // 避免浮点数运算
    }
    v[0] = v[n + 1] = 0; // 边界条件
    
    // 构建上凸包
    for (int i = 0; i <= n + 1; ++i) {
        // 维护凸包性质
        while (tp > 1) {
            int a = st[tp - 1], b = st[tp];
            // 判断点(i, v[i])是否使得凸包性质被破坏
            if ((v[i] - v[b]) * (b - a) > (v[b] - v[a]) * (i - b)) {
                tp--; // 移除不符合凸性的点
            } else {
                break;
            }
        }
        st[++tp] = i; // 将当前点加入凸包
    }
    
    // 计算每个位置的答案
    int t = 0; // 当前凸包线段的起始索引
    for (int i = 1; i <= n; ++i) {
        // 找到包含位置i的凸包线段
        while (t < tp && st[t + 1] <= i) {
            ++t;
        }
        
        if (st[t] == i) {
            // 当前位置是凸包顶点，直接跳下最优
            printf("%lld\n", v[i]);
        } else {
            // 当前位置在线段(st[t], st[t+1])上，线性插值
            int x = st[t], y = st[t + 1];
            // 插值公式：E[i] = ((y-i)*f(x) + (i-x)*f(y)) / (y-x)
            ll ans = ((y - i) * v[x] + (i - x) * v[y]) / (y - x);
            printf("%lld\n", ans);
        }
    }
    
    return 0;
}

3. 线性插值原理

对于位置 $i$ 在线段 $(x, y)$ 上，其中 $x < i < y$，期望值的计算基于线性插值：

$$E[i] = \frac{(y-i) \times f(x) + (i-x) \times f(y)}{y-x} $$

这个公式的直观理解：

• 线段 $(x, f(x))$ 到 $(y, f(y))$ 上的点可以表示为参数的线性组合
• 参数 $t = \frac{i-x}{y-x}$，则 $E[i] = (1-t) \times f(x) + t \times f(y)$
• 展开后得到上述公式

样例详细验证

输入样例：

2
1
3

处理过程：

步骤1：数据预处理

• $n = 2$
• $v[1] = 1 \times 10^5 = 100000$
• $v[2] = 3 \times 10^5 = 300000$
• $v[0] = 0$, $v[3] = 0$

序列为：$[0, 100000, 300000, 0]$

步骤2：构建凸包

考虑所有点：$(0,0), (1,100000), (2,300000), (3,0)$

1. 加入点 $(0,0)$：栈 $[0]$
2. 加入点 $(1,100000)$：
   • 检查：$(100000-0) \times (1-0) = 100000$，保持
   • 栈 $[0, 1]$
3. 加入点 $(2,300000)$：
   • 检查点 $(1,100000)$：$(300000-100000) \times (1-0) = 200000$，$(100000-0) \times (2-1) = 100000$
   • $200000 > 100000$，移除点 $(1,100000)$
   • 栈 $[0, 2]$
4. 加入点 $(3,0)$：
   • 检查点 $(2,300000)$：$(0-300000) \times (2-0) = -600000$，$(300000-0) \times (3-2) = 300000$
   • $-600000 < 300000$，保持
   • 栈 $[0, 2, 3]$

最终凸包顶点：$[0, 2, 3]$

步骤3：计算答案

对于 $i = 1$：

• 找到线段 $(0, 2)$
• $E[1] = \frac{(2-1) \times 0 + (1-0) \times 300000}{2-0} = 150000$

对于 $i = 2$：

• 在凸包顶点上，$E[2] = 300000$

输出：

150000
300000

算法正确性证明

1. 凸包性质保证最优性

定理：如果 $E$ 序列是 $f$ 序列的上凸包，那么对于所有 $i$，$E[i]$ 等于从位置 $i$ 出发的最优期望报酬。

证明思路：

1. 在凸包顶点上，$E[i] = f(i) > \frac{E[i-1] + E[i+1]}{2}$，直接跳下是最优选择
2. 在线段上，$E[i] = \frac{E[i-1] + E[i+1]}{2}$，继续移动是最优选择
3. 通过动态规划归纳可以证明这个解满足原递推方程

2. 单调栈算法的正确性

单调栈算法是计算凸包的标准方法：

• 按 $x$ 坐标顺序处理点
• 对于每个新点，检查是否破坏凸性
• 通过移除凹点来维护凸包性质

复杂度分析

时间复杂度：$O(N)$

• 构建凸包：每个点最多入栈和出栈一次，$O(N)$
• 计算答案：线性扫描，$O(N)$

空间复杂度：$O(N)$

• 存储原序列：$O(N)$
• 单调栈：$O(N)$

扩展与讨论

1. 为什么乘以 $10^5$？

题目要求输出期望值乘以 $10^5$ 后向下取整，这样：

• 避免浮点数运算，提高精度和效率
• 所有计算都可以用整数进行

2. 算法泛化

这种方法可以推广到类似的随机游走最优停止问题：

• 状态空间是线性的
• 转移概率对称
• 有即时报酬和继续选择的权衡

3. 实际意义

这个问题本质上是最优停止问题的一个特例，在金融数学（美式期权定价）、随机控制等领域有广泛应用。

总结

本题的解决体现了算法竞赛中几个重要的思维技巧：

1. 问题转化：将复杂的随机过程转化为几何问题
2. 数学洞察：发现期望序列的凸包性质
3. 算法选择：使用高效的单调栈算法
4. 实现优化：通过整数运算避免精度问题

通过凸包方法，我们将一个看似需要动态规划迭代的问题转化为 $O(N)$ 的高效解法，展现了算法设计的优美和力量。