bzoj1075

题意:

给你一个地图，问从x1,y1->x2,y2，要走的路最短，问

耗油和速度

题解：

首先把他们转到左下角->右上角

然后只能往上或往下

考虑到可能有小数

所以都乘上他们的公倍数

然后就是dp

代码：

#include<bits/stdc++.h>

using namespace std;

const int N=,M=;

const double inf=1e15;

int n,L,lcm,lim,i,j,k,p,x,y,a[N],b[N],xs,ys,xt,yt,t1,t2,ans1=-,ans2;

double f[][N][M],w[N];

int gcd(int a,int b){return b?gcd(b,a%b):a;}

void up(double&a,double b){if(a>b)a=b;}

int cal(int x)

{

      x*=;

      return x/lcm+(x%lcm>);

}

int main()

{

      scanf("%d%d",&n,&L);

      for (int i=;i<=;i++)w[i]=1.0*L/(80.0-0.75*i*i);

      for (int i=;i<=n;i++)scanf("%d",&a[i]),a[i]/=;

      for (int i=;i<=n;i++)scanf("%d",&b[i]),b[i]/=;

      for (int i=;i<=n;i++)x=max(max(a[i],b[i]),x);

      for (int i=lcm=;i<=x;i++)lcm=lcm*i/gcd(lcm,i);

      scanf("%d%d%d%d%d%d",&xs,&ys,&xt,&yt,&t1,&t2);

      lim=t2*lcm/;

      if (xs>xt)swap(xs,xt),swap(ys,yt);

      if (ys>yt)

     {

        for (int i=,j=n;i<j;i++,j--)swap(a[i],a[j]);

        ys=n-ys+,yt=n-yt+;

       }

      for (int j=ys;j<=yt;j++)

     for (int k=;k<=lim;k++)f[][j][k]=inf;

      f[][ys][]=;

      for (int i=xs;i<=xt;i++,p^=)

     {

        for (int j=ys;j<=yt;j++)

         for (int k=;k<=lim;k++)f[p^][j][k]=inf;

        for (int j=ys;j<=yt;j++)

         for (int k=;k<=lim;k++)

          if (f[p][j][k]<inf)

           {

              if (j<yt)

             for (int x=b[i];x;x--)

              {

                y=k+lcm/x*L;

                if (y<=lim)up(f[p][j+][y],f[p][j][k]+w[x]);

                }

              if (i<xt)

              for (int x=a[j];x;x--)

                {

                y=k+lcm/x*L;

                if (y<=lim)up(f[p^][j][y],f[p][j][k]+w[x]);

                  }

            }

       }

      for (int k=;k<=lim;k++)

     if (k*>=t1*lcm&&f[p^][yt][k]<inf)

      {

        if (ans1<)ans1=k;

        if (!ans2||f[p^][yt][k]+1e-<f[p^][yt][ans2])ans2=k;

        }

      if (ans1<)

     {

         puts("No");

         return ;

     }

      printf("%d %.2f\n%d %.2f",cal(ans1),f[p^][yt][ans1],

    cal(ans2),f[p^][yt][ans2]);

      return ;

}