当前位置: 首页 > news >正文

BZOJ1075 : [SCOI2007]最优驾车drive

设$f[i][j][k]$为到达$(i,j)$,用时为$\frac{k}{5lcm}$小时的最低耗油量,然后DP即可。

 

#include<cstdio>
const int N=12,M=210005;
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=-1,ans2;
double f[2][N][M],w[N];
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void swap(int&a,int&b){int c=a;a=b;b=c;}
inline void up(double&a,double b){if(a>b)a=b;}
int cal(int x){
  x*=12;
  return x/lcm+(x%lcm>0);
}
int main(){
  scanf("%d%d",&n,&L);
  for(i=1;i<=10;i++)w[i]=1.0*L/(80.0-0.75*i*i);
  for(i=1;i<=n;i++)scanf("%d",&a[i]),a[i]/=5;
  for(i=1;i<=n;i++)scanf("%d",&b[i]),b[i]/=5;
  for(i=1;i<=n;i++){
    if(x<a[i])x=a[i];
    if(x<b[i])x=b[i];
  }
  for(i=lcm=1;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/12;
  if(xs>xt)swap(xs,xt),swap(ys,yt);
  if(ys>yt){
    for(i=1,j=n;i<j;i++,j--)swap(a[i],a[j]);
    ys=n-ys+1,yt=n-yt+1;
  }
  for(j=ys;j<=yt;j++)for(k=0;k<=lim;k++)f[0][j][k]=inf;
  f[0][ys][0]=0;
  for(i=xs;i<=xt;i++,p^=1){
    for(j=ys;j<=yt;j++)for(k=0;k<=lim;k++)f[p^1][j][k]=inf;
    for(j=ys;j<=yt;j++)for(k=0;k<=lim;k++)if(f[p][j][k]<inf){
      if(j<yt)for(x=b[i];x;x--){
        y=k+lcm/x*L;
        if(y<=lim)up(f[p][j+1][y],f[p][j][k]+w[x]);
      }
      if(i<xt)for(x=a[j];x;x--){
        y=k+lcm/x*L;
        if(y<=lim)up(f[p^1][j][y],f[p][j][k]+w[x]);
      }
    }
  }
  for(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]+1e-9<f[p^1][yt][ans2])ans2=k;
  }
  if(ans1<0)return puts("No"),0;
  printf("%d %.2f\n%d %.2f",cal(ans1),f[p^1][yt][ans1],cal(ans2),f[p^1][yt][ans2]);
  return 0;
}

  

相关文章:

  • SharePoint自动化系列——Create a local user and add to SharePoint
  • iOS 轻量级的数据库leveldb
  • 混合的方式开启服务
  • JSDOM对象控制HTML元素
  • NSObject
  • android 环境搭建
  • AJAX 跨域请求 - JSONP获取JSON数据 jsson和jsonp
  • 点击失去焦点的文字
  • mac 终端 常用命令
  • HP ProLiant DL380 G6 服务器 - 清 BIOS 的方法
  • Mysql isam数据库恢复实战
  • A*寻路算法的探寻与改良(二)
  • 让透明div里的文字不透明
  • [原创]好买财富测试环境自动化发布部署系统实践
  • pptpd *** 老是连接不上内网排错
  • 3.7、@ResponseBody 和 @RestController
  • C++类中的特殊成员函数
  • CSS魔法堂:Absolute Positioning就这个样
  • Flannel解读
  • gcc介绍及安装
  • js学习笔记
  • Linux Process Manage
  • React组件设计模式(一)
  • Stream流与Lambda表达式(三) 静态工厂类Collectors
  • VUE es6技巧写法(持续更新中~~~)
  • 笨办法学C 练习34:动态数组
  • 创建一个Struts2项目maven 方式
  • 后端_ThinkPHP5
  • 机器学习 vs. 深度学习
  • 前端技术周刊 2019-01-14:客户端存储
  • 区块链共识机制优缺点对比都是什么
  • 如何优雅的使用vue+Dcloud(Hbuild)开发混合app
  • 如何优雅地使用 Sublime Text
  • 入口文件开始,分析Vue源码实现
  • 深入 Nginx 之配置篇
  • 我的面试准备过程--容器(更新中)
  • 移动端解决方案学习记录
  • 教程:使用iPhone相机和openCV来完成3D重建(第一部分) ...
  • ​​快速排序(四)——挖坑法,前后指针法与非递归
  • ​一些不规范的GTID使用场景
  • # 睡眠3秒_床上这样睡觉的人,睡眠质量多半不好
  • #define
  • ()、[]、{}、(())、[[]]等各种括号的使用
  • (42)STM32——LCD显示屏实验笔记
  • (C)一些题4
  • (附源码)计算机毕业设计ssm高校《大学语文》课程作业在线管理系统
  • (解决办法)ASP.NET导出Excel,打开时提示“您尝试打开文件'XXX.xls'的格式与文件扩展名指定文件不一致
  • (每日持续更新)jdk api之FileReader基础、应用、实战
  • (实战篇)如何缓存数据
  • (未解决)macOS matplotlib 中文是方框
  • *(长期更新)软考网络工程师学习笔记——Section 22 无线局域网
  • **登录+JWT+异常处理+拦截器+ThreadLocal-开发思想与代码实现**
  • . ./ bash dash source 这五种执行shell脚本方式 区别
  • ../depcomp: line 571: exec: g++: not found
  • .bat文件调用java类的main方法