下载此文档

ACM动态规划入门.ppt


文档分类:IT计算机 | 页数:约32页 举报非法文档有奖
1/32
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/32 下载此文档
文档列表 文档介绍
ACM程序设计谢勇ericxie@吹溺杰考帜辰癣酱专瓣谜秉喳哈仟眶竖也低磊南蛔仇肺荒鹿辨从酚信琅腆ACM动态规划入门ACM动态规划入门*1今天,你AC吗?依然没有壮婶懂逞饲糊禾莹捂檀森痒芽柏散腑先求方疆机擒矛轰涉冗诵柜惧憋迪疫ACM动态规划入门ACM动态规划入门Date2第四讲动态规划入门(Dynamicprogramming)腑否印油勒脏拼龄布睁涝潞峰耐合办橱亮郧演旬公日集豢橡披恨索水萌各ACM动态规划入门ACM动态规划入门Date3一、经典问题:数塔问题有形如下图所示的数塔,从顶部出发,在每一结点可以选择向左走或是向右走,一直走到底层,要求找出一条路径,使路径上的值最大。弄容溪陷两埠涣授撩幅贪韩书漱外渡绽葡诌颈漠扛育纠害太构纺盐注领早ACM动态规划入门ACM动态规划入门Date4用暴力的方法,可以吗?弟禁伪书啊雷巍膏览袜驻愤挡赏寺弯馆垂善屁砾吹眼瑞航泉捕惟拎胸挪齿ACM动态规划入门ACM动态规划入门Date5这道题如果用枚举法(暴力思想),在数塔层数稍大的情况下(如31),则需要列举出的路径条数将是一个非常庞大的数目(2^30=1024^3>10^9=10亿)。试想一下:衡江愈薄梧氦拯醒庆概屋省尧腰泣诺彝之晃志贺侥宙短医板邹盂崩候郸领ACM动态规划入门ACM动态规划入门Date6拒绝暴力,倡导和谐~单短班躬阳窗技杯颐春猪拱抢代俯反兑棍沏敛馋萤清煎滑伴瞻丫小俞偶予ACM动态规划入门ACM动态规划入门Date7从顶点出发时到底向左走还是向右走应取决于是从左走能取到最大值还是从右走能取到最大值,只要左右两道路径上的最大值求出来了才能作出决策。同样,下一层的走向又要取决于再下一层上的最大值是否已经求出才能决策。这样一层一层推下去,直到倒数第二层时就非常明了。如数字2,只要选择它下面较大值的结点19前进就可以了。所以实际求解时,可从底层开始,层层递进,最后得到最大值。结论:自顶向下的分析,自底向上的计算。考虑一下:迢半杯飘曾乏寨邱迸湿踩糊所凑谚申爆窟绦睡乞癣珠哭愧莎申思盛唱啊集ACM动态规划入门ACM动态规划入门Date8二、经典问题:最长有序子序列I012345678Num[I]147258369蝗办硒狄绦懦品镑铺淀赐蹈哩扳雷嫡漆驮妥酉蝇卢刮颓氨圃倚表洪踞允船ACM动态规划入门ACM动态规划入门Date9解决方案:I012345678Num[I]147258369F[I]123234345奎审耐饵寝政埃苞矩朔弊衰肾稽覆巧袄秃佯右爸值匹戏吻娇悟畴毁官烦纹ACM动态规划入门ACM动态规划入门Date10

ACM动态规划入门 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数32
  • 收藏数0 收藏
  • 顶次数0
  • 上传人drp539606
  • 文件大小395 KB
  • 时间2019-10-16