BISHI132　小红的地砖¶

简单通过率 69.15%python3样例通过牛客 AC

讲解章节：DP 入门

一句话

从第 1 块走到第 n 块，每步走 1 或 2 格，最小体力。

解题思路¶

这题考什么¶

BISHI131 的「最优化」版本：把「方案计数」的加法换成「求最优」的 min。

f_i = a_i + min(f_{i-1}, f_{i-2})

含义：走到第 i 块必然是从 i-1 或 i-2 迈过来的，走到哪一块都要付出 a_i。

数据规模与复杂度¶

n <= 1e5，O(n) 时间、O(1) 空间（滚动两个变量即可，不用开数组）。

坑在哪¶

n = 1 时答案是 0（保证 a_1 = 0，且不需要移动），要特判，否则 f_2 的边界会越界；
f_1 = a_1 = 0 是起点的体力（题目保证 a_1 = a_n = 0，但按 a_1 算更稳）；
f_2 只有一种来法（从第 1 块迈 1 步），不能套用 min(f_1, f_0) —— f_0 根本不存在。把 f_2 = a_1 + a_2 直接写成初值、递推从 i = 3 起步，就绕开了这条边界；n = 2 时循环一次都不转，答案正是这个初值。

参考实现¶

solutions/BISHI132.py
import sys


def main() -> None:
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))
    if n == 1:                               # 已经站在终点，一步都不用走
        sys.stdout.write("0\n")
        return
    f2 = a[0]                                # f_1
    f1 = a[0] + a[1]                         # f_2：只能从第 1 块迈一步过来
    # f1 始终是「刚算出的那一项」，f2 是它前面一项；下标 i 是 0 起的，对应 f_{i+1}。
    # 内联 min 写成条件表达式，比调用 min() 少一次函数调用，1e5 次下省得出来
    for i in range(2, n):
        f2, f1 = f1, a[i] + (f1 if f1 < f2 else f2)
    sys.stdout.write("%d\n" % f1)


main()

BISHI132 小红的地砖¶