1019 . E.Jumping Up

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

腦子裝咖哩
想像不出自己 AC 的題目是實作不出來的！雖然想像得出來也不一定可以就是了

User's AC Ratio

95.8% (251/262)

Submission's AC Ratio

38.6% (368/953)

Tags

CKsim 2015-CKsim-3rd DP

Description

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

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

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

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

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

Input Format

輸入檔的第一列有一個正整數T(1≤T≤1000)，代表接下來的測試資料總數。
接下來的每一列都是一組測試資料，首先會有一個正整數 N(2≤N≤1000)，接下來依序會有第一個鈴鐺到第N個鈴鐺相對於螢幕正中央的水平位移d1,d2,...,dN。其中任意的di都可以用有號的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
Submit
Back to Top