TopCoder

FHVirus
想像不出自己 AC 的題目是實作不出來的!

User's AC Ratio

96.8% (242/250)

Submission's AC Ratio

38.7% (358/925)

Tags

Description

玩過「兔子跳鈴鐺」的遊戲嗎?如果沒玩過,可以參考以下的網頁;p

http://www.ferryhalim.com/orisinal/g3/bells.htm

玩得過癮嗎:)
沒錯,這個問題就跟兔子跳鈴鐺有關。

有一顆超級大番茄(因為頭很大,所以簡稱大頭蕃)非常喜歡玩這個遊戲,可是每次滑鼠都要左移、右移,一不小心就會掉下去,又得從頭開始了,挺累人的說。遊戲中的兔子從跳上第一個鈴鐺開始,每次跳起來的最大高度只夠這隻兔子跳到下一個、或是第兩個鈴鐺上,而且鈴鐺一旦被踩過就會消失(然後兔子跳了起來)。現在給你 $n$個鈴鐺的水平位置,請你告訴大頭蕃從第一個鈴鐺開始一路跳到第 $n$個鈴鐺所需的最小移動水平距離總和為何?(我們在這個題目中假設可以踩的飛鳥不曾出現,而且不必每個鈴鐺都踩過。)

p.s.以上故事純屬虛構,但是測資並非虛構(不好笑…)

Input Format

輸入檔的第一列有一個正整數$T(1 \leq T \leq 1000)$,代表接下來的測試資料總數。
接下來的每一列都是一組測試資料,首先會有一個正整數 $N(2 \leq N \leq 1000)$,接下來依序會有第一個鈴鐺到第$N$個鈴鐺相對於螢幕正中央的水平位移$d_1,d_2,...,d_N$。其中任意的$d_i$都可以用有號的32-bit integer儲存。

Output Format

對於每一筆測試資料,請輸出一個正整數代表從第一個鈴鐺跳上第$N$個鈴鐺所需要的最小水平距離總長。

Sample Input 1

3
3 1 3 2
9 1 2 3 4 5 6 7 8 9
2 1 1

Sample Output 1

1
8
0

Hints

真的不會Overflow嗎?long long格式化輸出的話要用%lld喔!(笑)(或是用cout)

Problem Source

原TIOJ1019 / Problem Setter: Tmt

Subtasks

No. Testdata Range Score
1 0 50
2 1 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2