Time Limit: 1 second

Memory Limit: 64 MB

【问题描述】

晚会上大家在玩一款“暴力摩托”的游戏，它拥有非常逼真的画面和音响效果! 当然了，车子总是要加油的咯，已知赛道长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。

【输出格式】

输出一行，为最少用时（保留二位小数）

【数据规模】

Sample Input1

40 6

Sample Output1

0.53

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=u238

【题解】



这里先思考;

有没有可能在中间加一次油之后,

油还没耗尽继续加油?

加油?

要加到什么地步?

①如果和当前速度一样;

那么就等耗尽了再加就好.

②如果和当前速度相比更慢了

当前这段你先用高速开完再说啊

③如果和当前速度相比更快了

不行，不可能，因为速度是按照一次加油后的总油量来决定的

你不可能从20->6之后,加油变成100km/h

题意不允许;

综上，也就是说每一个位置决策完之后等到油耗尽之后再决策;

记忆化搜索;

设f[x]表示到第x位置花的最少时间;

写个dfs就好;

但是优先往远处走,这样f的约束性更强;



【完整代码】

#include <cstdio>

#include <algorithm>

#include <cmath>

#define rei(x) scanf("%d",&x)

#define rep1(i,x,y) for (int i = x;i <= y;i++)

#define rep2(i,x,y) for (int i = x;i >= y;i--)

using namespace std;

const int N = 1000+100;

const double tx[5] = {0,100.0,90.0,80.0,75.0};

int s,T;

double f[N];

void pre()

{

    rep1(i,0,1000)

        f[i] = 21e8;

}

void in()

{

    rei(s),rei(T);

    s/=10;

}

void dfs(int x,double t)

{

    if (t>=f[x]) return;

    f[x] = t;

    if (x==s)

        return;

    double key = double(T);

    if (x==0) key = 0;

    rep2(j,4,1)

    {

        int r = x+j;

        if (r>s) r = s;

        dfs(r,t+double(r-x)*10/tx[j]+key/60.0);

    }

    dfs(s,t+key/60.0+double(s-x)*10/70.0);

}

void o()

{

    printf("%.2f\n",f[s]);

}

int main()

{

    pre();//checked

    in();//checked

    dfs(0,0);//checked

    o();//checked

    return 0;

}