根据你提供的信息，这是一道动态规划题目，目标是求小红通过所有关卡后的**最大总收益**，每关选择左或右宝箱，考虑切换代价。 下面是使用 **Python 2** 编写的完整解决方案： ```python import sys def solve(): T = int(raw_input().strip()) for _ in range(T): n = int(raw_input().strip()) levels = [] for i in range(n): line = raw_input().split() a, b, c, d = map(int, line) levels.append((a, b, c, d)) # dp[i][0] 表示第 i 关（0-indexed）选择左边宝箱时的最大收益 # dp[i][1] 表示第 i 关选择右边宝箱时的最大收益 if n == 0: print(0) continue dp = [[-float('inf')] * 2 for _ in range(n)] # 第一关没有切换代价 dp[0][0] = levels[0][0] # 选左 dp[0][1] = levels[0][2] # 选右 for i in range(1, n): a, b, c, d = levels[i] prev_a, prev_b, prev_c, prev_d = levels[i-1] # 当前选择左边 # 来自上一关左边：无额外代价 # 来自上一关右边：需支付 dk-1，即 prev_d（注意：题目中 d_{k-1} 是从右切到左的代价） dp[i][0] = max(dp[i-1][0] + a, dp[i-1][1] + a - prev_d) # 当前选择右边 # 来自上一关右边：无额外代价 # 来自上一关左边：需支付 bk-1，即 prev_b dp[i][1] = max(dp[i-1][1] + c, dp[i-1][0] + c - prev_b) result = max(dp[n-1][0], dp[n-1][1]) print(result) if __name__ == '__main__': solve() ``` --- ### ✅ 说明： - **输入处理**：读取多组测试数据。 - **状态设计**： - `dp[i][0]`：在第 `i` 关选择**左侧宝箱**能获得的最大收益。 - `dp[i][1]`：在第 `i` 关选择**右侧宝箱**能获得的最大收益。 - **转移逻辑**： - 如果连续选择同一侧，无代价。 - 切换时减去对应的 `b` 或 `d`（注意是前一关的 `b` 或 `d`）。 - **初始化**：第一关无前置代价，直接取 `a` 或 `c`。 - **输出**：最后一关两种选择的最大值。 --- ### 📌 示例输入格式（供测试）： ``` 1 3 10 2 8 3 5 1 7 2 6 0 4 1 ``` 你可以将上述内容作为标准输入来测试程序。 --- ✅ 此代码适用于 Python 2 环境，已适配输入输出格式及题目逻辑。