1 条题解

  • 1
    @ 2022-9-5 22:40:56
    #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;
    }
    
    • 1

    信息

    ID
    3400
    时间
    2000ms
    内存
    125MiB
    难度
    7
    标签
    递交数
    1
    已通过
    1
    上传者