首頁  題目列表  狀態列表  排行榜  註冊  帳號: 密碼:
公告:支援C++11 (2014/08/18 21:39)
Problem 0071 : 卡卡跑丁車 
0071 -- 卡卡跑丁車 
Case Time Limit: 1000 ms    Memory Limit: 65536 KB
Total Testdata Count: 20
AC/Submit: 20/61    AC/Submit Users: 13/13

[回到列表]
題目敘述

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

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

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

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

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


輸入說明

  測試資料表示一場競賽的全程路線,其第一列有一個整數 $N$ ,代表接下來有幾條直線賽道,相鄰兩個直線賽道間恰有一個彎道。下一列有 $N$ 個非負整數,依序給出了每條直線賽道的長度。起點為第一條直線的首端,終點為最後一條直線的末端。

輸出說明

輸出卡卡到達終點所需的最短時間。

範例輸入

#1
5
10 10 10 10 10

#2
5
10 10 10 40 10


範例輸出

#1
120

#2
155


備註

所有測資組 : 賽道總長度 $\leq 2^{31} − 1$

測資組A : $1 \leq N \leq 3$
測資組B : $1 \leq N \leq 50$
測資組C : $1 \leq N \leq 1000$
測資組D : $1 \leq N \leq 3000$
測資組E : $1 \leq N \leq 8000$
測資組F : $1 \leq N \leq 10000$

測資

測資組A : 1~2 (2筆測資),5 分
測資組B : 3~5 (3筆測資),12 分
測資組C : 6~8 (3筆測資),25 分
測資組D : 9~10 (2筆測資),9 分
測資組E : 11~15 (5筆測資),32 分
測資組F : 16~20 (5筆測資),17 分
[回到列表]