试题、程序及解题报告oibh模拟赛report_第1页
全文预览已结束

付费下载

下载本文档

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

文档简介

1、OIBH2005/10/01 我们注意到题目中所求的递增数列中的每个数都是整数，且每个数字都是由不同的 3建立一个一一对应，使得数字k 的二进制表示与它所对应的三进制表示相同。举例说明：K k1111233449567 klonglong extended 0，up(i,j)表示(i,j)0，这样状态转移是显然的：f(i,j)=minf(i-1,j-1),up(i,j),left(i,j)+1 if(graphi,j=1) upi,jlefti,j的计算方法同一维部分和序列的DPO(n2)，考虑到空间的限制，可以用滚动数MLE 的问题，这同样是易于理解的。fii为根的子树所需要的最短时间。以根

2、节点root显然，对于边界值fleaf，即叶子节点而言，fleaf=1，但是对于非叶节点，问题就稍微复杂了一些。由于开始的时候我们只通知了rootroot root这里得知消息，并且我们假设root 所有儿子的f root 到底先通知那个儿 个儿子的f值最大我们先通知谁。这个是看起来很显然的结论。但是我们需要证明它。简略roots1,s2,s3,sn,fs1fs2fs3fsn.则我们要证明： ifsj.，通知这两颗子树的最短时间是 minfsi+i,fsj+j；当交换顺序以后，则通知这两个子树的最短时间是 Minfsi+j,ssj+i,fsifsj ji, 则我们交换顺序后的到的最小值显然不会

3、比原来fi=maxfsj+j sj i 的儿子。1 0 1 0 1 0 5651|0-1|0-1|0 1 0 - - - 1 0 - - - 1 0 NOI99有一道题目叫做棋盘分割（限于篇幅本人在此不再赘述此题的做法，大家可以P.116关于此题的分析）有些同学选择了和这题DP方法类似的状态表示和转移进行DPDP 是错误的。trivial O(n) 8 DP 的基础是什么呢？某个x1,x2,y1,y2的矩形中的切割边的方法来实现O(n)的状态转移，但是实际上这个结论是00000|0 00000|0 00000|0 00001|1 00|100|001|1000 00|0000 00|0000 这组数据用普通的DP2019，原因就在于最优切割方案中O(n5)DP 是错误

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

温馨提示

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

最新文档

评论

0/150

提交评论