NC20255. [SCOI2007]最优驾车DRIVE
描述
输入描述
输入第一行为两个整数n, L,第二行包含n个正整数，从南到北描述n条东西走向的街道的速度限制，第三行包 含n个正整数，从西到东描述n条南北走向的街道的速度限制。第四行包含六个正整数xs, ys, xt, yt, t1, t2.
输出描述
如果无解，输出No，否则输出两行，分别描述最早到达的方案（若有多种方案，选择其中最省油的）和最省油的方案（如果有多种方案，选择其中最早到达的）。
每种方案用两个数表示，第一个数表示到达时刻（单位：分钟 ，向上取整）；第二个数表示耗油量（单位：加仑，四舍五入保留两位小数）。
示例1
输入:
6 20 30 40 50 50 50 50 50 50 50 50 50 40 1 1 6 6 300 320
输出:
300 6.25 318 5.60
说明:
【样例说明】样例1的最快路线为以40英里/小时为速度匀速前进，路程为200英里，因此时间为5小时，每加仑示例2
输入:
8 2 10 20 20 30 10 20 10 10 10 20 20 30 10 20 10 20 6 8 2 4 10 39
输出:
No
C++11(clang++ 3.9) 解法, 执行用时: 112ms, 内存消耗: 33132K, 提交时间: 2020-04-01 20:56:15
#include<cstdio>
#include<iostream>
#define eps 1e-8
using namespace std;
const int N=12,M=210010;
const double INF=1e15;
int n,L,lcm,lim;
int a[N],b[N],xs,ys,xt,yt,t1,t2,ans1=-1,ans2;
double f[2][N][M],w[N];
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int recover(int x)
{
x*=12;
return x/lcm+(x%lcm>0);
}
int main()
{
scanf("%d%d",&n,&L);
for(int i=1;i<=10;i++)
w[i]=1.0*L/(80.0-0.75*i*i);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),a[i]/=5;
for(int i=1;i<=n;i++)
scanf("%d",&b[i]),b[i]/=5;
int cc=0;
for(int i=1;i<=n;i++)
{
if(cc<a[i]) cc=a[i];
if(cc<b[i]) cc=b[i];
}
for(int i=lcm=1;i<=cc;i++)
lcm=lcm*i/gcd(lcm,i);
scanf("%d%d%d%d%d%d",&xs,&ys,&xt,&yt,&t1,&t2);
lim=t2*lcm/12;
if(xs>xt) swap(xs,xt),swap(ys,yt);
if(ys>yt)
{
for(int i=1,j=n;i<j;i++,j--) swap(a[i],a[j]);
ys=n-ys+1,yt=n-yt+1;
}
for(int j=ys;j<=yt;j++)
for(int k=0;k<=lim;k++)
f[0][j][k]=INF;
f[0][ys][0]=0;
int p=0;
for(int i=xs;i<=xt;i++,p^=1)
{
for(int j=ys;j<=yt;j++)
for(int k=0;k<=lim;k++)
f[p^1][j][k]=INF;
for(int j=ys;j<=yt;j++)
for(int k=0;k<=lim;k++)
if(f[p][j][k]<INF)
{
if(j<yt)
for(int x=b[i];x;x--)
{
int t=k+lcm/x*L;
if(t<=lim)
f[p][j+1][t]=min(f[p][j+1][t],f[p][j][k]+w[x]);
}
if(i<xt)
for(int x=a[j];x;x--)
{
int t=k+lcm/x*L;
if(t<=lim)
f[p^1][j][t]=min(f[p^1][j][t],f[p][j][k]+w[x]);
}
}
}
for(int k=0;k<=lim;k++)
if(k*12>=t1*lcm&&f[p^1][yt][k]<INF)
{
if(ans1<0) ans1=k;
if(!ans2||f[p^1][yt][k]+eps<f[p^1][yt][ans2]) ans2=k;
}
if(ans1<0)
{
printf("No");
return 0;
}
printf("%d %.2f\n%d %.2f\n",recover(ans1),f[p^1][yt][ans1],
recover(ans2),f[p^1][yt][ans2]);
return 0;
}