某個遊戲要依序闖過n個關卡，初始的時候有一個幸運數字，每個關卡有兩個關卡數字，你必須把自己的幸運數字調整為兩個關卡數字之一，才能通過此關卡，調整的成本是你的幸運數字與關卡數字的差值(絕對值)。請計算出最低闖關總成本。
舉例來說，一開始的幸運數字為1，n=2，第一關的過關數字為(5, -5)，第二關的過關數字為(-3, -2)。要依序通過兩關，假設第一關把幸運數字調整成5，第二關調整為-2，則需要成本為|1–5|+|5–(-2)|=11。如果，第一關把幸運數字-5，第二關調整為-3，則需要成本為|1–(-5)|+|(-5)–(-3)|=8。你可以看得出來，總共有四種方式過關，其中最小成本是8。
第 一行 有兩 個正整數 n 與 t ，代表關卡數以及初 始幸運號碼 。 接下來有 n
行，每行兩個整數 依序代表每一關的過關數字。 n 1e5，過關數字的絕對值皆不超過1e4。
最小過關成本。
2 1 5 -5 -3 -2
8
3 0 -5 1 -8 3 -7 -7
9
我們以狀態轉移的方式來思考，有n個關卡要通過，每個關卡通過的成本跟上一關通過的方式有關，但是跟更早的無關。所以可以想成通過每一關有兩種狀態，達到第i關的第j種狀態的最低成本是cost[i][j]其中 i<=n而j=0或1。列出相鄰兩關的成本計算方式即可。
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||