b589. 超級馬拉松賽 -- SEARCC-ISSC國際學生程式設計競賽 | From: [106.1.117.161] | 發表日期 : 2024-10-08 00:58

每次跑步可以選擇加速，如果加速，本次得分 * 2, 但下一個跑道分數歸零

1. 構造問題: 跑步的最高得分

2. 定義狀態: f(i, state), 表示當前跑到第 i 個跑道,選擇 state 的最高得分

3. 求解小規模的簡單問題:

    f(0, 不跑) = 0

    f(0, 跑) = nums[0];

    f(0, 加速) = nums[0] * 2;

4. 狀態轉移方程式:

    f(i, 不跑) = max(f(i - 1, 不跑), f(i - 1, 跑), f(i - 1, 加速))

    f(i, 跑) = max(f(i - 1, 不跑), f(i - 1, 跑)) + nums[i];

    f(i, 加速) = max(f(i - 1, 不跑), f(i - 1, 跑)) + nums[i] * 2;

5. 判斷複雜度: O(n)