[動態規劃]NOIP模擬題 ：摩托車遊戲 carz 解題報告

[問題描述]

晚會上大家在玩一款“暴力摩托”的遊戲，它擁有非常逼真的畫面和音響效果，如疾馳而過的汽車呼嘯聲，摩托車的引擎聲和轉彎時輪胎與地面摩擦而產生的聲音。而且它在遊戲中加入了對抗成份，比賽中你可以使用拳、腳去干擾對方，使其落後於你，是不是很卑鄙啊 ? 遊戲中千萬不能手下留情，因爲對手會主動攻擊你。如果遇到開摩托車的警察，雖然也可以對他踢上一腳，但可得小心點呀，萬一被他們捉住了，那就 GAME OVER 啦!

當然了，車子總是要加油的咯，已知賽道長 S公里（S≤10000整數，且爲10的倍數），賽車的油耗Q=1，即 1公里 路耗 1個單位的油。Q不變，賽車的油箱爲無窮大，同時在沿途的任何地方都可以加油。 約定，每次加油的數量爲整數，且爲 10的倍數，賽車的速度與賽車加油後的總油量有關。其關係如下表列出：

加油量	車速（公里 / 時）
≤10	100
（ 10 ， 20 ]	90
（ 20 ， 30 ]	80
（ 30 ， 40 ]	75
（ 40 ， + ∞ ）	70

同時，汽車每加油一次需要耗費 T分鐘（T<=100不論加油多少，開始時的加油不計時間）

當 S，T給出之後，選擇一個最優的加油方案。使汽車以最少時間跑完全程。

例如：當 S=40，T=6（分鐘），加油的方案有許多種，列出一些：

1）起點加油40，用時40/75≈0.53小時

2）起點加油20，中途加20，用時20/90+20/90+6/60（化爲小時）≈ 0.54 小時

[輸入文件]

一行，爲兩個整數 S、T。

[輸出文件]

輸出一行，爲 最少用時（保留二位小數）

[輸入樣例]

40 6

[輸出樣例]

0.53

【分析】

區間動態規劃。

狀態設定： F[i]：前i*10公里的最小時間。

邊界條件：F[0]=0

狀態轉移方程： Min{ Min{F[j]+((i-j)*10)/speed+T/60} （1<=j<=i-1） , (i*10)/speed }  (其中藍色的是在起點加油的狀態，speed可以由題目中給的表格算出)。

目標狀態：F[S]。

【我的代碼】

#include <cstdio>
#include <iostream>
#include <cstdlib>
using namespace std;
int S,t;
double T;
double F[1001];//F[i]:前i*10公里的最小時間

double Speed(int oil)
{
    double ans;
    oil*=10;
    if(oil<=10)
        ans=100;
    if(oil>10 && oil<=20)
        ans=90;
    if(oil>20 && oil<=30)
        ans=80;
    if(oil>30 && oil<=40)
        ans=75;
    if(oil>40)
        ans=70;
    return ans;
}

void init()
{
    scanf("%d %d\n",&S,&t);
    S/=10;
    T=((double)(t))/(double(60));
    return;
}

void dp()
{
    for (int i=1;i<=S;i++)
    {
        double Min=10000000.0;
        double time;
      
        time=(i*10)/Speed(i);
        if(Min>time)
            Min=time;
      
        for (int j=1;j<=i-1;j++)
        {
            double speed=Speed(i-j);
            time=((i-j)*10)/speed;
            if(Min>(F[j]+time+T))
                Min=F[j]+time+T;
        }
        F[i]=Min;
    }
    printf("%.2lf",F[S]);
}

int main()
{
    freopen("carz.in","r",stdin);
    freopen("carz.out","w",stdout);
    init();
    dp();
    return 0;
}