集训队作业雷环中0096解题报告_第1页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

1、IOI2003中国国家集训队难题讨论活动0096 解题报告重庆外语学校 雷环中【题目大意】N头牛完成D圈比赛，每头牛初始精力同为E。其战术是一头领骑，其它追随，如团体速度为X圈/分，则领骑每分钟消耗精力X*X，追随的牛每分钟消耗精力X。领骑只能在整数分钟时进行交换，交换时间不计，最后只需一牛撞线。求完成比赛的最短时间，输出为整数。1N20，1D100，1E100。【解决情况】目前只有O(N*D2)的算法。应该能够进一步优化，但还没有找到。【算法梗概】动态规划【正文】这道题的动态规划算法比较明显。既然题目只要求一头牛撞线，那幺我们大可尽管总分利用前面不需要其撞线的牛。同时我们发现，对于追随的牛，

2、无论领跑的速度如何，它跑完M圈所需要的时间总是M。这就说明每次用来领跑的牛，只需用自己剩下的精力尽量跑就是了，跑完了就可以把它抛弃。这里，“尽量” 二字包含在一定的时间内跑最多的圈数和跑一定的圈数花最短的时间两方面问题。除此之外，题目还有可能无解。很容易发现，当且仅当时题目一定有解，否则奶牛们以最慢的速度或者以最省精力的方式都是跑不完的。如果定义为花去(这里的“花去”意为跑完后就下场)i头奶牛跑完j圈的最小时间，那么我们最后需要输出的结果就是。并且有状态转移方程：，其中。初始值，。这里，表示最多用精力i，跑完j圈的最短时间，其中。f的计算时间复杂度为O(N*D2)，下面我们着重考虑t的计算。我

3、们用表示在第1k分钟里奶牛的速度，那幺根据的定义，我们可以得到满足：存在，使得，且。根据广义均值不等式或者柯希不等式，我们很容易得出，于是我们就得到。然而这是错的，因为当时，但事实上，我们发现满足的并不存在，应该等于5 。其原因是根据得到的k只是其下限，并非的值。下面我们来考察需要满足什幺条件。显然，有，于是我们可以设中有m个，另外k-m个，。根据我们得到，。根据我们有，将代入并整理得： (*)上式即为需要满足的条件。于是，我们可以从开始从小到大枚举k，直到(*)式得到满足。最后让我们来分析计算t的时间复杂度。由于，所以计算的时间复杂度为O(T),其中T为E、D中较小者。于是计算t的时间复杂度为O(ET)。因此，算法的总时间复杂度为O(N*D2)，空间复杂度为O(ED)。【附录

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论