历年题目wc2008解题报告trip_第1页
历年题目wc2008解题报告trip_第2页
历年题目wc2008解题报告trip_第3页
历年题目wc2008解题报告trip_第4页
历年题目wc2008解题报告trip_第5页
已阅读5页，还剩8页未读， 继续免费阅读

下载本文档

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

文档简介

1、题意简述给出一个NM的非负矩阵要求从中选出一些方格使得：任意两个0权方格之间存在一条由选出方格组成的路径选出的所有方格权和最小范围：N, M, K(0权方格数目) = 10得分情况100分选手、承、韬、漆子超、平均分正式营员非正式营员64.2535.10算法搜索？贪心？动态规划？特殊数据K = 2，最短路NM = 20，枚举每个方格是否被选择K = 3，枚举两个点，最短路算法分析算法一：搜索将所有方格按照权值从小到大排序优先选择权值较小的进行搜索预计得分：30100算法分析算法二：基于连通性的状态压缩动态规划状态描述前x 1行以及第x行的前y列每列最后的一个方格，共6个方格之间的连通情况Fxy

2、S连通(x, y)456123算法分析算法二：基于连通性的状态压缩动态规划状态描述预先计算所有可能的连通情况 (每行110000左右)将所有可能的连通情况与自然数之间建立对应FxyS连通(x, y)456123算法分析算法二：基于连通性的状态压缩动态规划状态转移从FxyS出发枚举(x, y + 1)是否选取，进而更新S得到S 更新Fxy+1S 类似处理 (x + 1, 1)(x, y)4561234算法分析算法二：基于连通性的状态压缩动态规划时间复杂度：O(NMS)空间复杂度：O(NMS)预计得分：50100算法分析算法三：基于树结构的状态压缩动态规划一些显而易见的结论所选择的方块组成一棵树叶子结点都是0权方格算法分析算法三：基于树结构的状态压缩动态规划状态表示 状态描述的性质的根的位置 (x, y)中包含的0权结点 (2N状态压缩，记为T)FxyT算法分析算法三：基于树结构的状态压缩动态规划状态转移 两棵合并FxyT1 + FxyT2 FxyT1 T2根的延伸FxyT1 + costxy FxyT1 (x, y)算法分析算

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

温馨提示

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

最新文档

评论

0/150

提交评论