题解 | 宵暗的妖怪

def main():
    import sys
    input = sys.stdin.read().split()
    n = int(input[0])
    a = list(map(int, input[1:n+1]))
    
    # 边界情况：只有3段时，只能选这三段，得中间值
    if n == 3:
        print(a[1])
        return
    
    # 定义dp数组：dp[i] 表示前i个位置（0~i）能获得的最大饱食度
    dp = [0] * n
    # 初始化：
    # dp[0] = 0（只有1段，无法操作）
    # dp[1] = 0（只有2段，无法操作）
    # dp[2] = a[1]（前3段，选0-1-2，得a[1]）
    dp[2] = a[1]
    
    # 从第4个位置（i=3）开始遍历
    for i in range(3, n):
        # 状态转移：
        # 1. 不选包含i的三段 → 最大为dp[i-1]
        # 2. 选包含i的三段（即i-2, i-1, i）→ 得a[i-1] + dp[i-3]（前i-3个位置的最大值）
        dp[i] = max(dp[i-1], a[i-1] + dp[i-3])
    
    print(dp[-1])

if __name__ == "__main__":
    main()