从“小球落地”问题解析动态规划与图论建模的竞赛思维

1. 项目概述与核心思路

最近在带几个准备CSP-S复赛的学生集训，发现他们对于动态规划和图论这两大核心模块的理解，总是停留在“背模板”的阶段。一遇到稍微变化一点的题目，比如把经典的“爬楼梯”问题换个场景，或者在图论里加个条件，就不知道怎么下手了。这让我意识到，光讲理论是没用的，必须用具体的、甚至看起来“简单”的题目，去拆解背后的通用思维模型。

就拿这个“小球落地”问题来说，乍一看，这跟动态规划有什么关系？跟图论更是八竿子打不着。很多学生第一反应就是写个循环，累加一下完事。但如果你只看到这一步，那就错过了这道题真正的训练价值。在竞赛中，命题人经常会把一些经典的数学模型，包装成生活化、物理化的场景。你的任务就是“剥开”这层外衣，看到里面那个赤裸裸的“状态转移方程”。

这道题的价值在于，它是一个绝佳的“思维脚手架”。它简单到足以让你看清每一个步骤，但又完整地蕴含了“状态定义”、“状态转移”、“边界处理”这几个动态规划最核心的要素。同时，它还可以自然地引申到“决策过程建模为图”的图论思想。我们今天的目标，就是通过这个“小球”，把DP和图的抽象概念，变成你手里实实在在的、可复用的解题工具。我会用Python一步步实现，并告诉你，在赛场上遇到新题时，如何快速识别并套用这种思维模式。

2. 问题拆解：从物理过程到数学模型

我们先老老实实地把题目手算一遍，这个过程至关重要，它能帮你发现规律，而这个规律就是状态转移方程的雏形。

题目：一个小球从100米高度自由落下，每次落地后反弹回原高度的一半，再落下。求它在第10次落地时，总共经历了多少米，以及第10次反弹的高度。

2.1 手动模拟与规律发现

我们设初始高度H = 100米。

• 第1次落地：
  • 小球从100米落到地面，经过路程S1 = 100米。
  • 落地后反弹，反弹高度h1 = 100 / 2 = 50米。
• 第2次落地：
  • 小球需要从上次反弹的高度（50米）落下，所以先经历50米落地。
  • 此时总路程S2 = S1 + 50。
  • 落地后再次反弹，反弹高度h2 = 50 / 2 = 25米。
  • 但是！小球接下来还要从25米的高度再落下去，为第3次落地做准备。所以，从第2次落地到第3次落地之间，小球其实走了“上去再下来”的过程，即25 + 25 = 50米。这个路程需要计入第3次落地时的总路程。

看到这里，关键点就出来了：从第2次落地开始，每次“落地”这个事件发生时，小球走过的路程，都包含了“从上次反弹高度落下的路程”和“从上次落地到这次落地之间，它完成的一次完整‘上升-下降’循环的路程”。

更精确地说，对于第i次落地（i >= 2）：

1. 它首先完成了从第i-1次反弹高度h[i-1]的下降，距离为h[i-1]。
2. 然后，为了给第i次落地做准备，在第i-1次落地后，它反弹到了h[i]的高度，然后又从h[i]落下。这个过程的路程是2 * h[i]。

因此，如果我们定义：

• total_distance[i]：第i次落地时，小球经过的总路程。
• height[i]：第i次落地后，反弹的高度。

那么我们可以得到：

• 初始状态：
  • height[0] = H（这里我们把初始高度看作第0次“反弹”高度，方便计算）
  • total_distance[1] = H（第一次落地只经历了初始高度的下降）
• 状态转移：
  • height[i] = height[i-1] / 2（每次反弹高度减半）
  • total_distance[i] = total_distance[i-1] + height[i-1] + 2 * height[i]（i >= 2）
    • 解释：第i次的总路程 = 第i-1次的总路程 + 从第i-1次反弹高度落下的距离(height[i-1]) + 第i次落地前完成的完整“上升-下降”路程(2 * height[i])。

等等，这个公式对吗？我们验证一下i=2。 已知：total_distance[1]=100,height[1]=50,height[2]=25。 代入：total_distance[2] = 100 + 50 + 2*25 = 200。 手动计算：第一次落地100米，第二次落地前，小球从50米落下（50米），总路程150米。第二次落地后反弹到25米，再落下25米，为第三次落地做准备。所以到第二次落地时刻，总路程确实是100+50=150米。我们公式算出200米，显然错了。

注意：这里是一个经典的思维陷阱。我们混淆了“事件发生时刻”和“过程”。题目问的是“第10次落地时”，这个“时”指的是落地那一瞬间。在落地瞬间，小球刚刚走完“下降”过程，还没有开始“上升”。所以，对于第i次落地（i>=2），它只包含了从第i-1次反弹高度h[i-1]的下降过程。

2.2 正确的状态定义与转移

纠正后的定义：

• total_distance[i]：第i次落地瞬间，小球经过的总路程。
• rebound_height[i]：第i次落地后，反弹的高度。

推导：

• 第1次落地：total_distance[1] = H
• 第2次落地：小球走完了H（第一次下降） +rebound_height[1]（从第一次反弹高度下降）。所以total_distance[2] = H + rebound_height[1]。
• 第3次落地：小球走完了total_distance[2]+rebound_height[2]（从第二次反弹高度下降）。
• ……
• 通用公式（i >= 2）：
  • rebound_height[i] = rebound_height[i-1] / 2
  • total_distance[i] = total_distance[i-1] + rebound_height[i-1]

边界与初始：

• rebound_height[0] = H（我们可以把初始释放点想象成“第0次反弹”的高度，这样公式更统一）
• total_distance[1] = H
• 对于i从 1 到 n（n=10）：
  • rebound_height[i] = rebound_height[i-1] / 2
  • 如果i == 1:total_distance[i] = H
  • 否则:total_distance[i] = total_distance[i-1] + rebound_height[i-1]

看，这就是一个清晰的动态规划模型！rebound_height和total_distance就是我们的“状态”，它们依赖于前一个状态，并有明确的转移方程。我们成功地把一个物理问题，转化为了一个可计算的递推问题。

3. 动态规划（DP）实现与深度解析

现在我们用Python来实现上述的DP思路。我会给出两种常见的DP实现方式，并分析它们在竞赛中的适用场景。

3.1 基础递推法（自底向上）

这是最直观，也是效率最高（O(n)时间复杂度，O(n)空间复杂度）的实现方式。它清晰地体现了“先解决小问题，再解决大问题”的DP思想。

def ball_drop_dp_basic(H, n): """ 使用动态规划（递推）计算小球落地问题。 参数: H: 初始高度 (米) n: 第几次落地 (例如 10) 返回: total_distance: 第n次落地时总路程 rebound_height: 第n次落地后反弹高度 """ # 初始化状态数组 # rebound_height[i] 表示第i次落地后的反弹高度 rebound_height = [0] * (n + 1) # 多一位，方便下标对齐，rebound_height[0]表示初始高度 total_distance = [0] * (n + 1) # total_distance[i] 表示第i次落地时的总路程 # 边界条件（初始化） rebound_height[0] = H # 第0次“反弹”高度就是初始高度 total_distance[1] = H # 第1次落地，路程就是初始高度H # 状态转移（递推） for i in range(1, n + 1): # 计算第i次落地后的反弹高度 rebound_height[i] = rebound_height[i-1] / 2.0 # 计算第i次落地时的总路程 (i=1的情况已初始化) if i > 1: total_distance[i] = total_distance[i-1] + rebound_height[i-1] return total_distance[n], rebound_height[n] # 调用函数，计算第10次落地的情况 H = 100.0 n = 10 total_dist, rebound_h = ball_drop_dp_basic(H, n) print(f"【DP递推法】第{n}次落地时，总路程为：{total_dist:.6f} 米") print(f"【DP递推法】第{n}次反弹高度为：{rebound_h:.6f} 米")

运行这段代码，你会得到结果：

【DP递推法】第10次落地时，总路程为：299.609375 米 【DP递推法】第10次反弹高度为：0.097656 米

3.2 空间优化版递推（滚动数组）

在上面的代码中，我们使用了两个长度为n+1的数组来存储所有状态。但仔细观察状态转移方程：

• rebound_height[i]只依赖于rebound_height[i-1]
• total_distance[i]只依赖于total_distance[i-1]和rebound_height[i-1]

这意味着，在计算第i个状态时，我们只需要前一个状态（i-1）的信息。因此，我们可以用固定几个变量来“滚动”更新，将空间复杂度从 O(n) 降低到 O(1)。这在n非常大时（比如题目问第10000次落地）能节省大量内存。

def ball_drop_dp_optimized(H, n): """ 使用动态规划（空间优化版）计算小球落地问题。 使用滚动变量，空间复杂度O(1)。 """ # 初始化“前一个状态” prev_rebound = H # 代表 rebound_height[i-1]，初始为第0次反弹高度 current_total = H # 代表 total_distance[i]，初始为第1次落地路程 (i=1) # 如果n就是1，直接返回 if n == 1: return current_total, prev_rebound / 2.0 # 从第2次落地开始递推 for i in range(2, n + 1): # 计算当前次落地后的反弹高度（即第i次反弹高度） current_rebound = prev_rebound / 2.0 # 计算当前次落地时的总路程 current_total = current_total + prev_rebound # total_distance[i] = total_distance[i-1] + rebound_height[i-1] # 更新“前一个状态”，为下一次循环做准备 # 注意：循环下一次要计算的是第i+1次落地，其需要的“前一次反弹高度”就是本次刚算出的current_rebound prev_rebound = current_rebound # 循环结束后： # current_total 是 total_distance[n] # prev_rebound 是 rebound_height[n-1]？不对，循环内最后一步 prev_rebound = current_rebound， # 所以此时的 prev_rebound 是 rebound_height[n] # 但我们需要的是第n次落地后的反弹高度，也就是 rebound_height[n] final_rebound = prev_rebound return current_total, final_rebound # 调用验证 total_dist_opt, rebound_h_opt = ball_drop_dp_optimized(H, n) print(f"\n【DP空间优化法】第{n}次落地时，总路程为：{total_dist_opt:.6f} 米") print(f"【DP空间优化法】第{n}次反弹高度为：{rebound_h_opt:.6f} 米")

这个版本的结果应该和基础版完全一致。在竞赛中，如果题目对内存有严格要求，或者n的规模极大，这种优化是必须掌握的技能。

3.3 动态规划思维在本问题中的映射

让我们再回头审视一下，这个简单的问题是如何完美体现动态规划五部曲的：

1. 确定dp数组及下标的含义：我们定义了两个数组rebound_height[i]和total_distance[i]，下标i直接对应“第i次落地/反弹”这个阶段。这是最关键的一步，定义清晰，问题就解决了一半。
2. 确定递推公式：我们通过分析物理过程，得到了rebound_height[i] = rebound_height[i-1] / 2和total_distance[i] = total_distance[i-1] + rebound_height[i-1]。这就是我们的“状态转移方程”。
3. dp数组如何初始化：我们明确了rebound_height[0] = H和total_distance[1] = H。初始化是递推的起点，错了全盘皆输。
4. 确定遍历顺序：由于第i个状态依赖于第i-1个状态，所以我们必须从i=1开始，从前向后依次遍历。这是典型的“自底向上”填表法。
5. 举例推导dp数组：我们在第二部分“手动模拟”就是在做这件事。动手算几步，既能验证公式，也能帮你发现思路中的漏洞（比如我们之前犯的错误）。

实操心得：很多同学觉得DP难，是因为一上来就想写代码。我的建议是，至少花一半的时间在草稿纸上完成前四步。把状态定义、转移方程、初始化和遍历顺序都想明白、写清楚，代码只是水到渠成的翻译工作。这道题就是一个极好的训练：强迫自己用DP的框架去思考一个看似不需要DP的问题。

4. 图论视角：将过程建模为有向无环图（DAG）

如果你觉得动态规划已经够用了，那可能还没触及竞赛思维的天花板。接下来，我们尝试用一个更高级，但也更通用的视角——图论，来看待这个问题。这能帮你解决更复杂的一类“多阶段决策问题”。

4.1 如何将落地过程建模成图？

我们把小球运动的每个“状态”抽象成图中的一个“节点”。什么是状态？在这个问题里，一个完整的状态可以用(落地次数, 当前高度)来表示吗？不太合适，因为“当前高度”在上升和下降时不同。

更精妙的建模方式是：将“第i次落地瞬间”和“第i次反弹到最高点瞬间”分别视为两类节点。

• 节点L_i：表示第i次落地瞬间（i从1到10）。属性：此时的总路程S_i。
• 节点B_i：表示第i次反弹到最高点瞬间（i从0到9）。节点B_0就是起始点，高度为H。属性：此时的高度h_i。

那么，小球运动的过程，就是在这张图上沿着有向边行走：

1. 从B_0(高度H) 出发，下降到L_1。这条边的“权重”就是下降的距离H，它累加到L_1的总路程中。
2. 从L_1反弹到B_1(高度H/2)。这个过程虽然上升，但题目只关心落地时的总路程，所以这个“上升”过程的路程暂时不记录在“落地节点”上，而是蕴含在后续的下降中。
3. 从B_1下降到L_2。边的权重是h_1(即H/2)。L_2的总路程 =L_1的总路程 + 这条边的权重。
4. 从L_2反弹到B_2(高度H/4)。
5. ……
6. 以此类推，直到走到节点L_10。

我们发现，这张图是一个简单的链状结构：B_0 -> L_1 -> B_1 -> L_2 -> B_2 -> ... -> L_10。其中，所有从B节点到L节点的边（下降边）有权重（下降距离），所有从L节点到B节点的边（反弹边）权重为0（因为不直接贡献落地总路程）。

4.2 为什么说这是DAG上的动态规划？

我们的目标是求L_10节点的“总路程”属性。观察发现：

• 节点L_i的总路程，只依赖于前驱节点L_{i-1}的总路程，以及从B_{i-1}到L_i这条边的权重。
• 节点B_i的高度，只依赖于前驱节点L_i和固定的衰减规则（除以2）。

整个图没有环，是一个有向无环图（DAG）。在这种图上，我们可以按照拓扑顺序（在这里就是自然的时间顺序B_0, L_1, B_1, L_2, ...）来依次计算每个节点的属性。这本质上就是动态规划！每个节点的属性就是一个“状态”，节点间的边定义了“状态转移”的规则和代价。

4.3 Python实现：显式建图与拓扑递推

虽然这个问题用链式DP更简单，但为了展示图论建模的思想，我们可以显式地构建这个DAG，并用拓扑排序的思想来求解。

class Node: """图节点类""" def __init__(self, node_type, index, height=0.0): """ 初始化节点 :param node_type: 'B' 表示反弹最高点，'L' 表示落地瞬间 :param index: 序号 :param height: 节点对应的高度（对于B节点有意义，L节点可设为0） """ self.type = node_type self.index = index self.height = height # B节点的高度 self.total_distance = 0.0 # L节点的总路程属性 # 邻接表：存储从该节点出发的边 (target_node, weight) self.edges = [] def add_edge(self, target_node, weight): self.edges.append((target_node, weight)) def solve_by_graph_model(H, n): """ 使用图论模型（DAG）解决小球问题 """ nodes = {} # 1. 构建所有节点 # 创建B0节点 nodes['B0'] = Node('B', 0, H) nodes['B0'].total_distance = 0.0 # 起始点，总路程为0 for i in range(1, n + 1): # 创建Li节点（落地节点） nodes[f'L{i}'] = Node('L', i, 0.0) # 创建Bi节点（反弹节点），其高度由前一个落地节点决定，这里先创建，高度稍后设置 nodes[f'B{i}'] = Node('B', i, 0.0) # 2. 构建边并设置节点属性 # 从 B0 到 L1 的边 weight = nodes['B0'].height # 下降距离就是B0的高度 nodes['B0'].add_edge(nodes['L1'], weight) # 设置L1的总路程（从B0来的权重） nodes['L1'].total_distance = weight for i in range(1, n): # 设置Bi的高度（等于前一个反弹高度的一半，B0除外） # 实际上，Bi的高度 = B_{i-1}.height / 2 # 但根据我们的建模，Bi的高度是由Li反弹决定的，而Li反弹的高度是固定的衰减关系。 # 更准确的逻辑是：从Li到Bi的反弹过程，决定了Bi的新高度。 # 我们在这里简化：直接根据规则计算Bi的高度 prev_b_node = nodes[f'B{i-1}'] current_b_node = nodes[f'B{i}'] current_b_node.height = prev_b_node.height / 2.0 # 添加从 Li 到 Bi 的边（反弹边，权重为0，因为不增加总路程） nodes[f'L{i}'].add_edge(current_b_node, 0.0) # 添加从 Bi 到 L_{i+1} 的边（下降边） next_l_node = nodes[f'L{i+1}'] weight = current_b_node.height current_b_node.add_edge(next_l_node, weight) # 计算 L_{i+1} 的总路程 = L_i的总路程 + 从Bi到L_{i+1}的权重 nodes[f'L{i}'].total_distance = nodes[f'L{i}'].total_distance # 保持不变（实际上已在之前设置） next_l_node.total_distance = nodes[f'L{i}'].total_distance + weight # 处理最后一个反弹高度 Bn（第n次落地后的反弹） # Bn的高度 = B_{n-1}.height / 2 last_b_node = nodes[f'B{n}'] last_b_node.height = nodes[f'B{n-1}'].height / 2.0 # 最后一条从 Ln 到 Bn 的边（虽然我们不需要用它计算路程，但为了模型完整可以添加） nodes[f'L{n}'].add_edge(last_b_node, 0.0) # 3. 获取结果 final_total_distance = nodes[f'L{n}'].total_distance final_rebound_height = last_b_node.height return final_total_distance, final_rebound_height # 调用图论模型求解 total_dist_graph, rebound_h_graph = solve_by_graph_model(H, n) print(f"\n【图论模型法】第{n}次落地时，总路程为：{total_dist_graph:.6f} 米") print(f"【图论模型法】第{n}次反弹高度为：{rebound_h_graph:.6f} 米")

这个实现看起来比直接的DP复杂得多，但它揭示了一种强大的建模思想。对于更复杂的问题，比如小球每次反弹后可能以不同的比例（有时一半，有时三分之一）反弹，或者落地时有能量损失，这种状态机（图）模型就能轻松扩展。你可以通过修改add_edge的逻辑和节点属性的计算规则来适应新变化，而DP方程可能需要重新推导。

注意事项：在竞赛中，除非题目明显需要（如状态转移非常复杂、不规则），否则不建议对简单问题使用这种显式建图的方法，因为它编码复杂度高。但是，在思考阶段，用“状态作为节点，转移作为边”的图模型来梳理逻辑，是破解复杂DP问题的利器。这是一种高阶的思维训练。

5. 数学解析与公式直接求解

对于这个特定的问题，我们其实可以跳出编程思维，直接找到数学上的通项公式。这不仅能验证我们程序的结果，更能加深对问题本质的理解。

5.1 总路程的等比数列求和

让我们用数学语言重新表述： 设初始高度为H。 第i次落地后的反弹高度为：h_i = H / (2^i)。 第i次落地瞬间的总路程为S_i。

根据之前的分析：

• S_1 = H
• S_2 = S_1 + h_1 = H + H/2
• S_3 = S_2 + h_2 = H + H/2 + H/4
• ...
• S_n = H + H/2 + H/4 + ... + H/(2^(n-1))(对于 n >= 1)

看出来了么？从第二项开始，S_n是一个首项为H，公比为1/2的等比数列的前n项和，但注意项数：H是第1项，H/2是第2项，...，H/(2^(n-1))是第n项。

所以，S_n = H * (1 - (1/2)^n) / (1 - 1/2) = 2H * (1 - (1/2)^n)但是，这个公式计算的是H + H/2 + ... + H/(2^(n-1))的和。我们来验证一下n=1:S_1 = 2*100*(1-0.5)=100，正确。n=2:S_2=2*100*(1-0.25)=150，正确。

因此，第n次落地总路程的闭合公式为：S(n) = 2 * H * (1 - (1/2)^n)

5.2 第n次反弹高度的公式

这个更简单：rebound_height(n) = H / (2^n)

5.3 Python实现与验证

def ball_drop_math(H, n): """ 使用数学公式直接计算 """ total_distance = 2 * H * (1 - (0.5) ** n) rebound_height = H / (2 ** n) return total_distance, rebound_height # 调用验证 total_dist_math, rebound_h_math = ball_drop_math(H, n) print(f"\n【数学公式法】第{n}次落地时，总路程为：{total_dist_math:.6f} 米") print(f"【数学公式法】第{n}次反弹高度为：{rebound_h_math:.6f} 米") # 与DP结果对比，验证一致性 print(f"\n【一致性验证】") print(f"总路程差值：{abs(total_dist_math - total_dist):.10f}") print(f"反弹高度差值：{abs(rebound_h_math - rebound_h):.10f}")

数学公式法不仅代码极其简洁，而且计算效率是 O(1)，远高于DP的 O(n)。当n非常大时（比如上亿），DP循环会非常慢，而公式计算依然是瞬间完成。

实操心得：在解决竞赛问题时，养成“先寻找数学规律”的习惯。很多问题，尤其是数列、递推类问题，背后都有简洁的数学公式。找到它，不仅能快速解题，还能用于对拍，验证你DP或搜索算法的正确性。当然，不是所有问题都有闭合解，但尝试推导一下，本身就是对思维极好的锻炼。

6. 代码整合、测试与扩展思考

我们将几种方法整合到一个程序中，并进行测试和扩展思考。

6.1 完整代码示例与测试

def main(): H = 100.0 n = 10 print("小球落地问题 - 多种解法对比") print("="*50) # 解法1: 基础DP递推 total_dp, rebound_dp = ball_drop_dp_basic(H, n) print(f"1. 动态规划（递推）:") print(f" 第{n}次落地总路程: {total_dp:.8f} m") print(f" 第{n}次反弹高度: {rebound_dp:.8f} m") # 解法2: 空间优化DP total_opt, rebound_opt = ball_drop_dp_optimized(H, n) print(f"\n2. 动态规划（空间优化）:") print(f" 第{n}次落地总路程: {total_opt:.8f} m") print(f" 第{n}次反弹高度: {rebound_opt:.8f} m") print(f" 与基础DP结果一致: {abs(total_opt-total_dp)<1e-10 and abs(rebound_opt-rebound_dp)<1e-10}") # 解法3: 图论模型 (此处调用之前定义的函数，为简洁略去重复代码，实际运行需包含) # total_graph, rebound_graph = solve_by_graph_model(H, n) # print(f"\n3. 图论模型法:") # print(f" 第{n}次落地总路程: {total_graph:.8f} m") # print(f" 第{n}次反弹高度: {rebound_graph:.8f} m") # 解法4: 数学公式法 total_math, rebound_math = ball_drop_math(H, n) print(f"\n4. 数学公式法:") print(f" 第{n}次落地总路程: {total_math:.8f} m") print(f" 第{n}次反弹高度: {rebound_math:.8f} m") print(f" 与DP结果一致: {abs(total_math-total_dp)<1e-10 and abs(rebound_math-rebound_dp)<1e-10}") print("\n" + "="*50) print(f"最终答案（取公式法精确值）:") print(f" 第{n}次落地时，共经过 {total_math:.6f} 米") print(f" 第{n}次反弹 {rebound_math:.6f} 米高") if __name__ == "__main__": main()

6.2 扩展思考：如果问题变一下

竞赛题绝不会原封不动地考你背过的题。现在我们来做几个变式训练，看看如何运用刚才建立的思维模型。

变式1：求第10次“触地”（包括落地和弹起触碰地面）时，总共经过的路程。

注意：这里“触地”包括了“落地”和“弹起后再次触地”（即上升过程结束，开始下降的瞬间）。这相当于我们之前图模型中的每一个L节点（落地）和每一个从B节点下降触地的瞬间？不，弹起后触地就是下一次落地。仔细想，“第10次触地”就是“第10次落地”。但题目如果问“前10次触地”，那含义就不同了。我们按“第10次触地”就是“第10次落地”来理解，那么答案不变。如果问“从开始到第10次触地（包括上升和下降）”，那么总路程需要计算上升过程。这时，每次从L_i到B_i的上升距离h_i也要计入总路程。总路程公式变为：S_n = H + 2 * (H/2 + H/4 + ... + H/(2^(n-1))) = H + 2H*(1 - (1/2)^(n-1))。你需要敏锐地捕捉这种词语差异。

变式2：小球每次落地后，反弹高度变为上一次的k倍（0<k<1），求第n次落地总路程和反弹高度。

这就是我们DP模型和图模型优势所在了。只需要修改状态转移方程中的系数：

• DP:rebound_height[i] = rebound_height[i-1] * k
• total_distance[i]的递推关系不变。
• 数学公式：S(n) = H + 2Hk * (1 - k^(n-1)) / (1 - k)（当 k != 1/2 时，需重新推导等比数列求和） 用DP实现，几乎只需改动一行代码。

变式3：小球从高度H落下，每次落地后反弹回原高度的一半，再落下，求它从开始到最终静止（理论无限次）所经过的总路程。

这是一个无穷等比数列求和问题。总路程S = H + 2*(H/2 + H/4 + H/8 + ...) = H + 2H*(1/2 + 1/4 + 1/8 + ...)。括号内是一个公比为1/2的无穷等比数列，其和为(1/2) / (1 - 1/2) = 1。所以S = H + 2H*1 = 3H = 300米。这给出了一个有趣的极限结果：无论反弹多少次，小球的总路程不会超过初始高度的3倍。

6.3 常见错误与排查技巧

在实现和调试这类问题时，新手常犯以下错误：

1. 循环边界错误：最容易把循环次数搞错。如果从i=1循环到n来计算第n次落地，要清楚i代表的是当前次还是上一次。画出一个简单的状态转移表（如下），是避免边界错误的最佳方法。

i (落地次数)	反弹高度 h(i-1)	总路程 S(i)	计算公式
1	H (初始)	H	S(1)=H
2	H/2	H + H/2	S(2)=S(1)+h(1)
3	H/4	H + H/2 + H/4	S(3)=S(2)+h(2)

2. 变量类型错误：在Python中，如果H是整数（如100），那么H/2在Python 3中会是浮点数50.0，这没问题。但如果你用了//（整除），或者在其他语言中（如C++）没有注意数据类型，就会得到错误结果（100/2=50，但100//2=50，后续50//2=25也没问题，但如果你期望小数，就会出错）。安全起见，对于涉及除法的计算，初始值建议用浮点数100.0。

3. 精度问题：虽然本题对精度要求不高，但要知道浮点数计算存在微小的误差。在比较两个浮点数是否相等时，不要用==，而应该判断两者差的绝对值是否小于一个极小值（如1e-10）。我们的验证代码就采用了这种方法。

4. 题意理解偏差：如前所述，对“第10次落地时”的“时”字理解不准，可能会错误地加上下一次的上升路程。务必仔细读题，最好用自己的话复述一遍题意。

这道“小球落地”题，就像一颗棱镜。从不同角度（直接模拟、DP、图论、数学公式）去看，会折射出不同的光彩。在CSP-S的备战中，我强烈建议你多做这种“一题多解”的深度剖析。它锻炼的不是编码能力，而是问题转化能力和建模能力。当你拿到一个崭新的、令人望而生畏的题目时，这种能力能帮你迅速将它与你脑海中已有的模型（如今天的DP状态机、DAG）联系起来，从而找到突破口。记住，竞赛比的不是谁写的代码多，而是谁能在更短的时间内，看穿问题的本质。