题解 P4469 【[SCOI2007]最优驾车】

William_Fangs · 2019-08-26 18:40:21 · 题解

//因为要走最短路,所以只能向前,不能退后
//可以用DP来做
//dp[i][j]表示在x轴走了i步,y轴走了j步
//emm。。。
//但路径有多条,所以还要加一维不然无法表示当前状态
//加时间？加油？
//80-0.03v^2/l，明显不行
//只能加时间
//但时间也不好表示
//可以注意到 V一定是5的倍数
//并且v≤ 50
//所以可以将v/5,此时v只能为1~10
//所以 时间就成了l/(1~10)
//将时间乘以(1~10)的公倍数化为整数,即可表示
//判断时时间就是 t/(2520*5) *60，就是所花的时间
//则dp[i][j][k]表示在x轴走了i步,在y轴走了j步,用时为k时的耗油量
//k<=20*2520
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
#define dd double
#define inf 1e50
const int N=12;
const int M=2*N*2520;
ll gbs=2520;
ll n,m;
ll vx[N];
ll vy[N];
ll sx,sy;
ll tx,ty;
ll t1,t2;
ll tt[51];
ll len;
dd dp[N][N][M];//打了我两个多小时 wysl 
ll px,py;//direction
ll qz(dd aa)
{
    aa=-aa;
    ll myint=(ll)aa;
    return -myint;
}
inline dd oil_(ll ve)
{
    return (dd)len/(80-0.03*ve*ve);
}
inline void minn(double &a, const double &b)
{
    if (b < a) a = b;
}
inline ll judge(dd aa)
{
    if(fabs(aa)<1e-8)//精度处理
    {
        return 0;
    }
    else
    {
        if(aa>=0)
            return 1;
        else
            return -1;
    }
}
void work()
{
    if(tx>sx)
    {
        px=1;
    }
    else
        px=-1;
    if(ty-sy>0)
    {
        py=1;
    }
    else
        py=-1;
    ll dx=abs(tx-sx);
    ll dy=abs(ty-sy);
    dp[0][0][0]=0;
    for (int i = 0; i <= dx; ++i)
        for (int j = 0; j <= dy; ++j)
            for (int t = 0; t < M; ++t)
            {
                if (dp[i][j][t] != inf)
                {
                    static int x, y, nex, ney;
                    x = i + 1, y = j;
                    if (x <= dx)
                    {
                        ney = sy + y * py;
                        for (int v = 1; v * 5 <= vx[ney] && t + tt[v] < M; ++v)
                            minn(dp[x][y][t + tt[v]], dp[i][j][t] + oil_(v * 5));
                    }
                    x = i, y = j + 1;
                    if (y <= dy)
                    {
                        nex = sx + x * px;
                        for (int v = 1; v * 5 <= vy[nex] && t + tt[v] < M; ++v)
                            minn(dp[x][y][t + tt[v]], dp[i][j][t] + oil_(v * 5));
                    }
                }
            }

    ll mt=-1;
    ll mo=-1;
    for (int i=0; i<M; i++)
    {
        if (dp[dx][dy][i] !=inf)
        {
            double ti = (double)i * len/2520*N;
            if (judge(ti-t1)>=0&&judge(t2-ti)>=0)
            {
                if(mt==-1)
                {
                    mt=i;
                }
                if(mo==-1)
                {
                    mo=i;
                }
                else if(judge(dp[dx][dy][i]-dp[dx][dy][mo])==-1)
                {
                    mo=i;
                }
            }
        }
    }
    if(mt==-1)
    {
        printf("No\n");
        return ;
    }
    printf("%lld %.2lf\n", (ll)ceil((double)mt*len/2520*N),dp[dx][dy][mt]);//使时间单位变成分钟
    printf("%lld %.2lf\n", (ll)ceil((double)mo*len/2520*N),dp[dx][dy][mo]);
    return ;
}
signed main()
{
    //memset(dp)
    scanf("%lld%lld",&n,&len);
    for(int i=0; i<n; i++)
    {
        scanf("%lld",&vx[i]);
    }
    for(int i=0; i<n; i++)
    {
        scanf("%lld",&vy[i]);
    }
    scanf("%lld%lld%lld%lld%lld%lld",&sx,&sy,&tx,&ty,&t1,&t2);
    sx--;
    sy--;
    tx--;
    ty--;
    for(int i=1; i<=10; i++)
    {
        tt[i]=2520/i;
    }
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            for(int k=0; k<M; k++)
            {
                dp[i][j][k]=inf;
            }
        }
    }
    work();
    return 0;
}