回分類題庫
h073: B.卡卡跑丁車
關鍵字: NPSC 2010 高中組初賽

測資點 : 2 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 50 Times / 36 Users | Submit : 137 Times / 39 Users | Accepted rate : 92%
題目加入時間 : 2012-11-04 02:20

Content: 简体中文

「卡卡跑丁車」是一款最新型的賽車遊戲,由超可愛的角色、超酷炫的跑丁車陪你一起軋車甩尾,操作簡單容易上手,輕鬆休閒不麻煩!你只要在遊戲中,使用小技巧陷害對手,讓自己在時間內跑完全程,就可以獲得勝利唷!

在遊戲中遇到彎道時,通常需要減速以求安全過彎,而跑丁車提供了另一個選擇—甩尾!!雖然甩尾會使過彎速度下降,但累積三次甩尾後便可換取一個加速器,可以大幅縮減通過直線的時間!!可惜的是,當你囤積了兩個未使用的加速器後,再次甩尾並不會被累積計算。

卡卡是一名跑丁車玩家,由於缺乏經驗經常拿不到第一名。他最大的問題就是不清楚應該何時甩尾與使用加速器。他請你寫一個程式來提醒他在正確的地點做正確的事。

神奇的是卡卡平常通過任何彎道都需要 5 單位時間,若甩尾過彎則需平常的兩倍,也就是 10 單位時間。對於直線賽道來說,每通過 1 單位長度需要 2 單位的時間,若使用加速器則所需時間減半。

當然卡卡只會在彎道甩尾、直線使用加速器,並且一個彎道只能甩尾一次、一個加速器僅作用於一條直線賽道。

Input:

測資包含多組測試資料,第一列有一個整數 T 表示接下來有幾組測試資料。

每組測試資料表示一場競賽的全程路線,其第一列有一個整數 N,代表接下來有幾條直線賽道,相鄰兩個直線賽道間恰有一個彎道。下一列有 N 個非負整數,依序給出了每條直線賽道的長度。起點為第一條直線的首端,終點為最後一條直線的末端,賽道的總長度不會超過 231-1 (1 <= N <= 10000)。

Output:

對每筆測試資料輸出卡卡到達終點所需的最短時間。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
2
5
10 10 10 10 10
5
10 10 10 40 10

Sample Output :

120
155

Hint :

Author :

NPSC 2010 高中組初賽 (管理員:sagit)

  Solve it!   Status Forum