d072: Q-6-4. 闖關二選一
Tags : DP
Accepted rate : 16人/17人 ( 94% ) [非即時]
評分方式:
Tolerant

最近更新 : 2020-12-20 11:48

Content

某個遊戲要依序闖過 n 個關卡,初始的時候有一個幸運數字,每個關卡有兩個關卡數

字,你必須把自己的幸運數字調整為兩個關卡數字之一,才能通過此關卡,調整的成

本是你的幸運數字與關卡數字的差值(絕對值)。請計算出最低闖關總成本。

舉例來說,一開始的幸運數字為 1,n=2,第一關的過關數字為(5, -5),第二關的

過關數字為(-3, -2)。要依序通過兩關,假設第一關把幸運數字調整成 5,第二關

調整為-2,則需要成本為$|1-5|+|5-(-2)|=11$。如果,第一關把幸運數字-5,第

二關調整為-3,則需要成本為$|1-(-5)|+|(-5)-(-3)|=8$。你可以看得出來,總共

有四種方式過關,其中最小成本是 8。

Input

第一行有兩個正整數 $n$ 與 $t$,代表關卡數以及初始幸運號碼。接下來有 $n$

行,每行兩個整數,依序代表每一關的過關數字。$n ≤ 10^5$,過關數字的絕對值皆不

超過 $10^4$。

Output

最小過關成本。

Sample Input
//case 1
2 1
5 -5
-3 -2
//case 2
3 0
-5 1
-8 3
-7 -7
Sample Output
//case 1
8
//case 2
9
測資資訊:
記憶體限制: 64 MB
公開 測資點#0 (20%): 1.0s , <1M
公開 測資點#1 (20%): 1.0s , <1M
公開 測資點#2 (20%): 1.0s , <10M
公開 測資點#3 (20%): 1.0s , <10M
公開 測資點#4 (20%): 1.0s , <10M
Hint :
Tags:
DP
出處:
AP325 [管理者:
TCIRC ($\mathbb{TCFSH}\mathtt{Computer}\mathsf{Information}\mathit{Club}$)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」