[ZJ][DP] d944. B. 卡卡跑丁車＠Morris' Blog

2013-01-24 09:51:07| 人氣462| 回應0 | 上一篇 | 下一篇

[ZJ][DP] d944. B. 卡卡跑丁車

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

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

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

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

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

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

輸入說明：

測資包含多組測試資料，第一列有一個整數 T 表示接下來有幾組測試資料。每組測試資料表示一場競賽的全程路線，其第一列有一個整數 N ，代表接下來有幾條直線賽道，相鄰兩個直線賽道間恰有一個彎道。下一列有 N 個非負整數，依序給出了每條直線賽道的長度。起點為第一條直線的首端，終點為最後一條直線的末端，賽道的總長度不會超過 2³¹ − 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;
}

我要檢舉

#d944#B. 卡卡跑丁車

台長： Morris

您可能對以下文章有興趣

[ZJ] a361. A. 賓果遊戲

[ZJ][KM算法] d210. 老問題

b094. H. 數字拼盤 (IDA* 版本)

b207. F. 世界盃

人氣(462) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: NPSC |
此分類下一篇:[ZJ][翻轉處理] a315. D 滿州國皇帝之璽
此分類上一篇:[ZJ][KM算法] d210. 老問題

回應(0)