自动搬运

查看原文

来自洛谷，原作者为

	William_Fangs 桃李春风一杯酒 江湖夜雨十年灯

搬运于2025-08-24 22:00:30，当前版本为作者最后更新于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;
}