2013-01-24 09:51:07Morris
[ZJ][DP] d944. B. 卡卡跑丁車
內容 ：
「卡卡跑丁車」是一款最新型的賽車遊戲，由超可愛的角色、超酷炫的跑丁車陪你一起軋車甩尾，操作簡單容易上手，輕鬆休閒不麻煩！你只要在遊戲中，使用小技巧陷害對手，讓自己在時間內跑完全程，就可以獲得勝利唷！
在遊戲中遇到彎道時，通常需要減速以求安全過彎，而跑丁車提供了另一個選擇一甩尾！！雖然甩尾會使過彎速度下降，但累積三次甩尾後便可換取一個加速器，可以大幅縮減通過直線的時間！！可惜的是，當你囤積了兩個未使用的加速器後，再次甩尾並不會被累積計算。
卡卡是一名跑丁車玩家，由於缺乏經驗經常拿不到第一名。他最大的問題就是不清楚應該何時甩尾與使用加速器。他請你寫一個程式來提醒他在正確的地點做正確的事。
神奇的是卡卡平常通過任何彎道都需要 5 單位時間，若甩尾過彎則需平常的兩倍，也就是 10 單位時間。對於直線賽道來說，每通過 1 單位長度需要 2 單位的時間，若使用加速器則所需時間減半。
當然卡卡只會在彎道甩尾、直線使用加速器，並且一個彎道只能甩尾一次、一個加速器僅作用於一條直線賽道。
輸入說明
：
測資包含多組測試資料，第一列有一個整數 T 表示接下來有幾組測試資料。每組測試資料表示一場競賽的全程路線，其第一列有一個整數 N ，代表接下來有幾條直線賽道，相鄰兩個直線賽道間恰有一個彎道。下一列有 N 個非負整數，依序給出了每條直線賽道的長度。起點為第一條直線的首端，終點為最後一條直線的末端，賽道的總長度不會超過 231 − 1 (1 ≤ N ≤ 10000)。
輸出說明
：
對每筆測試資料輸出卡卡到達終點所需的最短時間。
範例輸入 ：
2 5 10 10 10 10 10 5 10 10 10 40 10
範例輸出 ：
120 155
提示
：
出處
：
2010 NPSC 高中組初賽
(管理：pcshic)
/**********************************************************************************/
/* Problem: d944 "B. 卡卡跑丁車" from 2010 NPSC 高中組初賽 */
/* Language: CPP (1594 Bytes) */
/* Result: AC(32ms, 964KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-01-24 09:32:04 */
/**********************************************************************************/
#include <stdio.h>
#include <algorithm>
using namespace std;
#define oo 1LL<<60
int main() {
int t, n;
long long x, dp[10000][3][3];
/* [012],[012] 甩尾次數 氮氣*/
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int i, j, k;
for(i = 0; i < n; i++)
for(j = 0; j < 3; j++)
for(k = 0; k < 3; k++)
dp[i][j][k] = oo;
scanf("%lld", &x);
dp[0][0][0] = 2*x;
for(i = 1; i < n; i++) {
scanf("%lld", &x);
for(j = 0; j < 3; j++) {
for(k = 0; k < 3; k++) {
dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k]+5+2*x);
if(j-1 >= 0) //僅甩
dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-1][k]+10+2*x);
if(k+1 < 2) //僅噴
dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k+1]+5+x);
if(j-1 >= 0 && k+1 < 2) //甩後噴
dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-1][k+1]+10+x);
}
}
dp[i][0][0] = min(dp[i][0][0], dp[i-1][2][0]+10+x);
dp[i][0][1] = min(dp[i][0][1], dp[i-1][2][0]+10+2*x);
dp[i][0][1] = min(dp[i][0][1], dp[i-1][2][1]+10+x);
dp[i][0][2] = min(dp[i][0][2], dp[i-1][2][1]+10+2*x);
}
long long res = oo;
for(i = 0; i < 3; i++)
for(j = 0; j < 3; j++)
res = min(res, dp[n-1][i][j]);
printf("%lld\n", res);
}
return 0;
}
/**********************************************************************************/
/* Problem: d944 "B. 卡卡跑丁車" from 2010 NPSC 高中組初賽 */
/* Language: CPP (1594 Bytes) */
/* Result: AC(32ms, 964KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2013-01-24 09:32:04 */
/**********************************************************************************/
#include <stdio.h>
#include <algorithm>
using namespace std;
#define oo 1LL<<60
int main() {
int t, n;
long long x, dp[10000][3][3];
/* [012],[012] 甩尾次數 氮氣*/
scanf("%d", &t);
while(t--) {
scanf("%d", &n);
int i, j, k;
for(i = 0; i < n; i++)
for(j = 0; j < 3; j++)
for(k = 0; k < 3; k++)
dp[i][j][k] = oo;
scanf("%lld", &x);
dp[0][0][0] = 2*x;
for(i = 1; i < n; i++) {
scanf("%lld", &x);
for(j = 0; j < 3; j++) {
for(k = 0; k < 3; k++) {
dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k]+5+2*x);
if(j-1 >= 0) //僅甩
dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-1][k]+10+2*x);
if(k+1 < 2) //僅噴
dp[i][j][k] = min(dp[i][j][k], dp[i-1][j][k+1]+5+x);
if(j-1 >= 0 && k+1 < 2) //甩後噴
dp[i][j][k] = min(dp[i][j][k], dp[i-1][j-1][k+1]+10+x);
}
}
dp[i][0][0] = min(dp[i][0][0], dp[i-1][2][0]+10+x);
dp[i][0][1] = min(dp[i][0][1], dp[i-1][2][0]+10+2*x);
dp[i][0][1] = min(dp[i][0][1], dp[i-1][2][1]+10+x);
dp[i][0][2] = min(dp[i][0][2], dp[i-1][2][1]+10+2*x);
}
long long res = oo;
for(i = 0; i < 3; i++)
for(j = 0; j < 3; j++)
res = min(res, dp[n-1][i][j]);
printf("%lld\n", res);
}
return 0;
}