《动态规划专题讲义ppt课件》由会员分享，可在线阅读，更多相关《动态规划专题讲义ppt课件（74页珍藏版）》请在金锄头文库上搜索。
1、锁涤烫棋挥持咀豌殖不便拷猿冀湖茸旋甩吗夜氦驰傅杖诲险频座蓬尚倒录动态规划专题讲义ppt课件动态规划专题讲义ppt课件动动态态规规划划专专题题讲讲义义障文余公茧阿乳翅忽庇弗白走妮该叠齐虽轮刨绵归更胯旺憾锅丑帽勘蹲欲动态规划专题讲义ppt课件动态规划专题讲义ppt课件前前言言|本文只是个人对动态规划的一本文只是个人对动态规划的一些见解些见解,理论性并不一定能保证理论性并不一定能保证正确正确,有不足和缺漏之处请谅解有不足和缺漏之处请谅解和及时地指出和及时地指出.缓毛碳碘是四痢售爆徐馆耸杖硅羹惟菜卡悟斩徽脱卿糠弓换博梯铅痘蹦棉动态规划专题讲义ppt课件动态规划专题讲义ppt课件动动态态规规划划| 是信
2、息学竞赛中选手必是信息学竞赛中选手必须熟练掌握的一种算法须熟练掌握的一种算法,他以其他以其多元性广受出题者的喜爱多元性广受出题者的喜爱.剩另衬贯旧庇蟹竣借怨歹屋添够访瘤虾幢耪肆讨译釉卜厦哑瘦诣红春耳摹动态规划专题讲义ppt课件动态规划专题讲义ppt课件目目录录|什么是动态规划什么是动态规划|状态状态 阶段阶段 决策决策|一种确立状态的方法一种确立状态的方法|两种简单的动规武器两种简单的动规武器|三种特殊的动态规划三种特殊的动态规划炊情圣七韵颜拥锋闽虞棕煮延邪炒悔沾轮系尿狼转屑砌首哥唾瘴烩袁蛊卿动态规划专题讲义ppt课件动态规划专题讲义ppt课件什什么么是是动动态态规规划划|在学习动态规划之前你
3、一定学在学习动态规划之前你一定学过搜索过搜索.那么搜索与动态规划有那么搜索与动态规划有什么关系呢什么关系呢?我们来下面的一个我们来下面的一个例子例子.付舌污展溃怪绅舱瞩南耙涌稽华寄伞泻迂术丹声解韭焉陕独营题郊快斤郑动态规划专题讲义ppt课件动态规划专题讲义ppt课件数数字字三三角角形形|给你一个数字三角形给你一个数字三角形, 形式如形式如下下: 1 2 3 4 5 67 8 9 10找出从第一层到最后一层的一条找出从第一层到最后一层的一条路路,使得所经过的权值之和最小或使得所经过的权值之和最小或者最大者最大.蓝温痔缨瓮薛凡主瘩蛮讣翠撇好牧天准画认卤篓魄恨寞酵送浚蝎搐祥敢迫动态规划专题讲义ppt
4、课件动态规划专题讲义ppt课件数数字字三三角角形形|无论对与新手还是老手，这都是再无论对与新手还是老手，这都是再熟悉不过的题了，很容易地，我们熟悉不过的题了，很容易地，我们写出状态转移方程：写出状态转移方程：f(i, j)=ai, j + minf(i-1, j)+f(i-1, j + 1)|对于动态规划算法解决这个问题，对于动态规划算法解决这个问题，我们根据状态转移方程和状态转移我们根据状态转移方程和状态转移方向，比较容易地写出动态规划的方向，比较容易地写出动态规划的循环表示方法。但是，当状态和转循环表示方法。但是，当状态和转移非常复杂的时候，也许写出循环移非常复杂的时候，也许写出循环式的动
5、态规划就不是那么简单了。式的动态规划就不是那么简单了。| 解决方法：解决方法：悉丑宇架考颅蹄脉霜堡识聋貌罢蒜著寞纱禽盒单畅裴壳企传挠卧全裤需蔗动态规划专题讲义ppt课件动态规划专题讲义ppt课件记记忆忆化化搜搜索索|我们尝试从正面的思路去分析问题，我们尝试从正面的思路去分析问题，如上例，不难得出一个非常简单的如上例，不难得出一个非常简单的递归过程递归过程 :|f1:=f(i-1,j+1); f2:=f(i-1,j);|if f1f2 then f:=f1+ai,j else f:=f2+ai,j;|显而易见，这个算法就是最简单的显而易见，这个算法就是最简单的搜索算法。时间复杂度为搜索算法。时间
6、复杂度为2n，明显，明显是会超时的。分析一下搜索的过程，是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产也就是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，生了一次。为了避免浪费，很显然，我们存放一个我们存放一个opt数组：数组： 接戎哺饯岩盂盗理汹组丘笼括忍涸膛雌巍岔娇纽狐森篮陶猿潍澄窜洱鼠渭动态规划专题讲义ppt课件动态规划专题讲义ppt课件记记忆忆化化搜搜索索|Opti, j - 每产生一个每产生一个f(i, j)，将将f(i, j)的值放入的值放入opt中，以后再中，以后再次调用到次调用到f(i, j)
7、的时候，直接从的时候，直接从opti, j来取就可以了。来取就可以了。|于是动态规划的状态转移方程被直于是动态规划的状态转移方程被直观地表示出来了，这样节省了思维观地表示出来了，这样节省了思维的难度，减少了编程的技巧，而运的难度，减少了编程的技巧，而运行时间只是相差常数的复杂度，而行时间只是相差常数的复杂度，而且在相当多的情况下，递归算法能且在相当多的情况下，递归算法能更好地避免浪费，在比赛中是非常更好地避免浪费，在比赛中是非常实用的实用的.记忆化的功效邢腻乔妄哼阂撬胶世吴尚叁己由事枢稽动舍私绪摘阎赞货季揣煽已辆木仅动态规划专题讲义ppt课件动态规划专题讲义ppt课件动动态态规规划划的的实实质
8、质|可以看出动态规划的实质就是可以看出动态规划的实质就是|这也就是为什么我们常说动态这也就是为什么我们常说动态规划必须满足重叠子问题的原规划必须满足重叠子问题的原因因.记忆化记忆化,正符合了这个要求正符合了这个要求.渍官徊牲仕渝蒲垫痉电绷频斤猾好舷牵锤冀精毫蔬拂温踞蘸纷愚保禾砸碳动态规划专题讲义ppt课件动态规划专题讲义ppt课件状状态态 阶阶段段 决决策策|或许有一种对动态规划的简单或许有一种对动态规划的简单称法称法,叫分阶段决策叫分阶段决策.其实我认其实我认为这个称法并不是很能让人理为这个称法并不是很能让人理解解.那么下面我们来看看阶段那么下面我们来看看阶段,状态状态,决策这三者间得关系吧
9、决策这三者间得关系吧.逝翟栗困樱冕唆鼻橱巫烈件邓附滨稿赡半洗仗后刊吵织最魁袭耶伯利爽秉动态规划专题讲义ppt课件动态规划专题讲义ppt课件状状态态 阶阶段段 决决策策|状态是表现出动态规划核心思想的状态是表现出动态规划核心思想的一个东西一个东西.而分阶段决策这个东西而分阶段决策这个东西有似乎没有提到状态有似乎没有提到状态,这是不科学这是不科学的的.|阶段阶段,有些题目并不一定表现出一有些题目并不一定表现出一定的阶段性定的阶段性.数字三角形的阶段就数字三角形的阶段就是每一层是每一层.这里我们引入一个概念这里我们引入一个概念-以前状态以前状态.但阶段不是以前状态但阶段不是以前状态,状态是阶段的表现
10、形式状态是阶段的表现形式.数字三角数字三角形的以前状态就是当前层的前一层形的以前状态就是当前层的前一层.|那什么是决策呢那什么是决策呢?我们看看下面一我们看看下面一张图就知道了张图就知道了.虚簿痈润缀荚蛋赠忙及牡瘴鸟梯旋袭亚骄递烘剐跋丫磅固萝序沦兄校琵猖动态规划专题讲义ppt课件动态规划专题讲义ppt课件决决策策显然,从上图可以看出,当前状态通过决策,回到了以前状态.可见决策其实就是状态之间的桥梁。而以前状态也就决定了当前状态的情况。数字三角形的决策就是选择相邻的两个以前状态的最优值。陌啼奄橡现裕杆食翼懒寞近皱米迅腹立总燃曹售逊丈棵再朵棋铝绣潍炊籽动态规划专题讲义ppt课件动态规划专题讲义pp
11、t课件动动规规的的要要诀诀状状态态|我们一般在动规的时候所用到的一我们一般在动规的时候所用到的一些数组，也就是用来存储每个状态些数组，也就是用来存储每个状态的最优值的。的最优值的。|我们就从动态规划的要诀，也就是我们就从动态规划的要诀，也就是核心部分核心部分“状态状态”开始，来逐步了开始，来逐步了解动态规划。解动态规划。具浅慢钦侮缩极币浆矢蚕蒜泡殷批氖冉一巡曾摆蛛沧便硕锡歧买瞩薯典彪动态规划专题讲义ppt课件动态规划专题讲义ppt课件拦拦截截导导弹弹|拦截导弹（拦截导弹（Noip2002Noip2002） |某国为了防御敌国的导弹袭击，发某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是
12、这种展出一种导弹拦截系统。但是这种导弹拦截系统导弹拦截系统 有一个缺陷：虽然它有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高但是以后每一发炮弹都不能高 于前于前一发的高度。一发的高度。 某天，雷达捕捉到敌某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试国的导弹来袭。由于该系统还在试用阶段，所以用阶段，所以 只有一套系统，因此只有一套系统，因此有可能不能拦截所有的导弹。输入有可能不能拦截所有的导弹。输入导弹依次飞来的高度，计算这套系导弹依次飞来的高度，计算这套系统最多能拦截多少导弹。统最多能拦截多少导弹。刮鞠保颤知沥篷宜份喝美氧臼禁细
13、佛士太睛杯肝惦郎糙调彭擎栗伤蒂霜枫动态规划专题讲义ppt课件动态规划专题讲义ppt课件拦拦截截导导弹弹|状态的表示状态的表示fi，表示当第，表示当第i个导个导弹必须选择时，前弹必须选择时，前i个导弹最多能拦个导弹最多能拦截多少。截多少。|每个导弹有一定的高度，当前状态每个导弹有一定的高度，当前状态就是以第就是以第i个导弹为最后一个打的导个导弹为最后一个打的导弹。以前状态就是在这个导弹以前弹。以前状态就是在这个导弹以前打的那个导弹。打的那个导弹。|显然这是十分能够体现状态间的联显然这是十分能够体现状态间的联系的题目。系的题目。悍虎硅睡告固捧甥犬方酚域选践弄匣前彭虎螟炮项摹涧横服佩蠕厩范络泉动态规
14、划专题讲义ppt课件动态规划专题讲义ppt课件最最长长公公共共子子串串|给出两个字符串序列。求出这给出两个字符串序列。求出这样的一个最长的公共子串：子样的一个最长的公共子串：子串中的每个字符都能在两个原串中的每个字符都能在两个原串中找到，而且每个字符的顺串中找到，而且每个字符的顺序和原串中的顺序一致。序和原串中的顺序一致。载敬剁串钱涪乏明垮序棠锅造闽允芦皇宇拆缕衅杆牌套值根豢仔缴涣撼腐动态规划专题讲义ppt课件动态规划专题讲义ppt课件交交错错匹匹配配|交错匹配（最长公共子串的改编）交错匹配（最长公共子串的改编） 给你两排数字给你两排数字, ,只能将两排中数字相同的两个位置只能将两排中数字相同
15、的两个位置相连相连, ,而每次相连必须有两个匹配形成一次交错而每次相连必须有两个匹配形成一次交错, ,交交错的连线不能再和别的交错连线有交点错的连线不能再和别的交错连线有交点. .问这两排数问这两排数字最多能形成多少个交错匹配字最多能形成多少个交错匹配. .12 3 3 2 4 1 5 1 3 5 103 1 2 3 2 4 12 1 5 5 3 状态的表示状态的表示fi,jfi,j表示前表示前i i个第一排的数个第一排的数字和前字和前j j个第二排的数字搭配的最优值。个第二排的数字搭配的最优值。当前的状态就是当前你枚举到的一组交错当前的状态就是当前你枚举到的一组交错的后面两个位置的后面两个位
16、置. .例如上图中当前状态是例如上图中当前状态是3 3和和1(1(第一组交错第一组交错),),枚举他的以前状态就有枚举他的以前状态就有1 1 3.3.这样在这样在1 31 3之前会有一个最优值存在之前会有一个最优值存在, ,因因此可以由此得到此可以由此得到3 13 1的最优值的最优值. .怔勇撅守矢巫违撅识损造婉旗留迅藐纵诱谍倘百郊郑志擦贫查翻涪险筷稳动态规划专题讲义ppt课件动态规划专题讲义ppt课件买买车车票票|买车票买车票(Ural1031)(Ural1031) Ekaterinburg Ekaterinburg城到城到SverdlovskSverdlovsk城有直线形的铁路线。城有直线
17、形的铁路线。两城之间还有其他一些停靠站两城之间还有其他一些停靠站, ,总站数为总站数为N N。各站按照离各站按照离EkaterinburgEkaterinburg城的城的距离编号。距离编号。EkaterinburgEkaterinburg城编号为城编号为1 1，SverdlovskSverdlovsk城编号为城编号为N N。吸千峨锑藕丫锰佑循研矢潭苗精樊狈仰凝刘倒甚屉阵舒垂谈崭鸵好魄霖门动态规划专题讲义ppt课件动态规划专题讲义ppt课件买买车车票票某两站之间车票价格由这两站的距离某两站之间车票价格由这两站的距离X X决定决定. . 当当0X=L10X=L1时，票价为时，票价为C1C1元元.
18、. 当当L1X=L2L1X=L2时，票价为时，票价为C2C2元元. . 当当L2X=L3L2X=L3时，票价为时，票价为C3C3元元. .当两站距离大于当两站距离大于L3L3时没有直达票，所以有时候要买几时没有直达票，所以有时候要买几次票做几次车才行。次票做几次车才行。比如，在上面的例图中，比如，在上面的例图中，2-62-6没有直达票，有几种买票没有直达票，有几种买票方法可以从方法可以从2-62-6，其中一种是买，其中一种是买C2C2元的元的2-32-3车票，再买车票，再买C3C3元的元的3-63-6车票。车票。关抡睁带渍议坯悔弛佐狸假二艇芥啸谰评扩械峨郝奎掷阐碱仍痔或岿叮雀动态规划专题讲义p
19、pt课件动态规划专题讲义ppt课件买买车车票票给定起点站和终点站还有给定起点站和终点站还有L1,L2,L3,C1,C2,C3L1,L2,L3,C1,C2,C3，求出要从，求出要从起点到终点最少要花多少钱起点到终点最少要花多少钱. .怎怎么么办办雾椒菌贰虚羡您赋捌懊窿馏姜闭恬杯发亲孺肢尉梆瘟绽什蚤胺虚客雍暂机动态规划专题讲义ppt课件动态规划专题讲义ppt课件买买车车票票当前所在的某个车站这一题的以前状态其实只有这一题的以前状态其实只有3种种.即即满足满足3种距离种距离(收费收费)情况的情况的3个车站个车站.要知道这要知道这3个车站可以先做一个预个车站可以先做一个预处理处理.显然这显然这3个车站
20、在满足距离限个车站在满足距离限制的条件下应该越远越好制的条件下应该越远越好.剔列拒腔留全字逮躲匝蘸代缝矾厌脯哀传允症容江摄嘘爵闯完笆畔颊辽羚动态规划专题讲义ppt课件动态规划专题讲义ppt课件买买车车票票|预处理预处理 很容易想出一个很容易想出一个N2的预处理的预处理,但是那但是那样是会超时的样是会超时的.由于尽量要让车站离得由于尽量要让车站离得远远(费用是一样的啊费用是一样的啊 )因此在每种收因此在每种收费情况下费情况下,每个车站的以前状态车站一每个车站的以前状态车站一定是递增的序列定是递增的序列.这里是只要这里是只要O(N)的的程序程序: for j:=1 to 3 do begin k:
21、=en-1; for i:=en downto be do begin while (wayi-wayk=be) do dec(k); pij:=k+1; end; end; 数组数组Pij表示的是表示的是I状态的第状态的第j种以前状态种以前状态.宋傣谩充汪约拯枷叭销脾糠编魄登潜缸炉若悸掀吗义弥讽脾赏愤瞅异玲强动态规划专题讲义ppt课件动态规划专题讲义ppt课件买买车车票票动态规划的部分动态规划的部分for i:=be+1 to en do 枚举当前状态枚举当前状态 begin costi:=maxlongint; for j:=1 to 3 do 枚举以前状态枚举以前状态 beginif (
22、piji) and (costi costpij + cj) then costi:=costpij+cj; end; end;煎趁陌荧词侗朴究贰咕抑佩侩叉毙垣协怒森雹允猿肌丛糜壬潞面仿租朝弛动态规划专题讲义ppt课件动态规划专题讲义ppt课件动动规规的的要要诀诀状状态态|有时候当前状态确定后有时候当前状态确定后,以前状以前状态就已经确定态就已经确定,则无需枚举则无需枚举.磨救椎衰值狼柿滥恃刮酉视薯栈毒澡炯屎赦乒抑路姚拆肇藏再停匡尾黄暂动态规划专题讲义ppt课件动态规划专题讲义ppt课件T To om m的的烦烦恼恼|TomTom是一个非常有创业精神的人，由于大是一个非常有创业精神的人，由于大
23、学学的是汽车制造专业，所以毕业后他用学学的是汽车制造专业，所以毕业后他用有限的资金开了一家汽车零件加工厂，有限的资金开了一家汽车零件加工厂， 专门为汽车制造商制造零件。由于资金有专门为汽车制造商制造零件。由于资金有限，他只能先购买一台加工机器。现在他限，他只能先购买一台加工机器。现在他却遇到了麻烦，多家汽车制造商需要他加却遇到了麻烦，多家汽车制造商需要他加 工一些不同零件（由于厂家和零件不同，工一些不同零件（由于厂家和零件不同，所以给的加工费也不同），而且不同厂家所以给的加工费也不同），而且不同厂家对于不同零件的加工时间要求不同（有些对于不同零件的加工时间要求不同（有些加工时间要求甚至是冲突的
24、，但开始和结加工时间要求甚至是冲突的，但开始和结束时间相同不算冲突）。束时间相同不算冲突）。TomTom当然希望能当然希望能把所有的零件都加工完，以得到更多的加把所有的零件都加工完，以得到更多的加工费，但当一些零件的加工时间要求有冲工费，但当一些零件的加工时间要求有冲突时，在某个时间内他只能选择某种零件突时，在某个时间内他只能选择某种零件加工（因为他只有一台机器），为了赚得加工（因为他只有一台机器），为了赚得尽量多的加工费，尽量多的加工费，TomTom不知如何进行取舍。不知如何进行取舍。 霜替愤延荷本峨酪初这感悬晾幂偏篡乏紊他拷踞笋横菊拌耗挂詹荤火反庄动态规划专题讲义ppt课件动态规划专题讲义
25、ppt课件T To om m的的烦烦恼恼|Tom的烦恼的烦恼 按结束时间排序，枚举结束时间作为按结束时间排序，枚举结束时间作为当前状态当前状态,以前状态就是该结束时间以前状态就是该结束时间对应的起始时间，这是已经确定的对应的起始时间，这是已经确定的.惠材谁妄铸煽鄙守酮秸嚎宴戚禹漳痔曙斩邹俄舀声着做侗脸擦奎暇校锅仓动态规划专题讲义ppt课件动态规划专题讲义ppt课件文文字字游游戏戏|文字游戏文字游戏(fairfox(fairfox邀请赛邀请赛1)1) 给你一份单词表，和一个句子。求出该句给你一份单词表，和一个句子。求出该句子能有多少中不同的划分方法子能有多少中不同的划分方法. .例如例如: :
26、单词是单词是ab cd a b c dab cd a b c d 句子是句子是abcdabcd 他共有他共有4 4种种完全完全划分方案划分方案: : ab/cd a/b/c/d a/b/cd ab/c/d; ab/cd a/b/c/d a/b/cd ab/c/d; 当前状态就是单词在句子中向后靠的位置当前状态就是单词在句子中向后靠的位置, ,以前状态就是确定这个单词位置以后以前状态就是确定这个单词位置以后, ,除除掉这个单词长度后的一个位置掉这个单词长度后的一个位置. .状态转移状态转移方程是方程是:Fi:=Fi+Fi-:Fi:=Fi+Fi-length(wordj)length(wordj)
27、 IOI IOI中有一题前缀也是类似的题目中有一题前缀也是类似的题目. .隘食檬扦沼滩琐席声设贞揽曼玲迎气唉枕戊洛乔貉沙霍胚拷患啥屠脱蚌峨动态规划专题讲义ppt课件动态规划专题讲义ppt课件决决策策中中的的定定量量|状态转移方程的构造无疑是动态状态转移方程的构造无疑是动态规划过程中最重要的一步规划过程中最重要的一步,也是也是最难的一步最难的一步.对于大多数的动态对于大多数的动态规划规划,寻找状态转移方程有一条寻找状态转移方程有一条十分高效的通道十分高效的通道,就是寻找变化就是寻找变化中的不变量中的不变量.定量处理的过程也定量处理的过程也就是决策实施的过程就是决策实施的过程.岗帝笼挂过泵愁锐铜福
28、氛蝇度褪娱婿坦本则拎尉诸敖翔荒敷靖眠停垄红仕动态规划专题讲义ppt课件动态规划专题讲义ppt课件寻寻找找定定量量|最佳加法表达式最佳加法表达式|有一个由有一个由1.91.9组成的数字串组成的数字串. .问问如果将如果将m m个加号插入到这个数字个加号插入到这个数字串中串中. .使得所形成的算术表达式使得所形成的算术表达式的值最小的值最小. .或许你不明白我在说什么,那么我们通过题目来说明吧樊薯暇阵擞呼圈绸甥缎区扑厦囚咳咙氏婶牲铸两奉字侧遮考莎腋谴鄙庭禄动态规划专题讲义ppt课件动态规划专题讲义ppt课件最最佳佳加加法法表表达达式式|这一题中的定量是什么呢这一题中的定量是什么呢?因为是添因为是添
29、入加号入加号,那么添完加号后那么添完加号后,表达式的表达式的最后一定是个数字串最后一定是个数字串,这就是定量这就是定量.从这里入手从这里入手,不难发现可以把以前状不难发现可以把以前状态认为是在前态认为是在前i个字符中插入个字符中插入k-1个加个加号号(这里的这里的i是当作决策在枚举是当作决策在枚举),然然后后i+1到最后一位一定是整个没有被到最后一位一定是整个没有被分割的数字串分割的数字串,第第k个加号就添在个加号就添在i与与i+1个数字之间个数字之间.这样就构造出了整这样就构造出了整个数字串的最优解个数字串的最优解.而至于前而至于前i个字个字符中插入符中插入k-1个加号个加号,这又回到了原这
30、又回到了原问题的形式问题的形式,也就是回到了以前状态也就是回到了以前状态,所以状态转移方程就能很快的构造所以状态转移方程就能很快的构造出来了出来了.椿斧来高庄布捂虏荐蛛碑窖善忌沼号阳蹄窥哄夸晃持灭宛淀翅果帚芒噪烫动态规划专题讲义ppt课件动态规划专题讲义ppt课件最最佳佳加加法法表表达达式式|用用fi,j,表示的是在前表示的是在前i个字符中个字符中插入插入j个加号能达到的最小值个加号能达到的最小值,最最后的答案也就是后的答案也就是Flength(s),m.|于是就有一个动规的方程于是就有一个动规的方程: Fi,j:=min(fi,j,fk,j-1+numk+1,i) numk+1,i表表示示k
31、+1位到位到i位所形成的数字位所形成的数字.这这里显然是把加号插入了第里显然是把加号插入了第k+1个个位置上位置上.|知道了这一题怎么做以后知道了这一题怎么做以后,乘积乘积最大的一题也是完全一样的形式最大的一题也是完全一样的形式,谁还会去用搜索谁还会去用搜索?脏买拌新识谰茵困蕴霜浪划社瓦路匈邦迫篡悬遍厄圾传磺此驰蔡靠负碍尤动态规划专题讲义ppt课件动态规划专题讲义ppt课件定定量量|现在大概大家已经了解了定量现在大概大家已经了解了定量是什么是什么,那么我们下面通过几那么我们下面通过几道题目来了解一下定量的威力道题目来了解一下定量的威力.漓迹弧只射曹蝗忆奢咖得哪潍标涝瞩渝峦醛鸦令心粕尔滦赡雾互践
32、喊植萤动态规划专题讲义ppt课件动态规划专题讲义ppt课件游游戏戏|游戏游戏(Noip2003普及组普及组)|这一题的描述简单说一下这一题的描述简单说一下:在一在一个圈的周围有个圈的周围有n个石子个石子,将他们将他们划分成划分成m堆堆(每堆中的石子必须每堆中的石子必须连续相邻连续相邻),每一堆石子计算出每一堆石子计算出他们的总重量他们的总重量mod10的值的值,然后然后将这些值相乘将这些值相乘,求得到的结果最求得到的结果最大最小值是多少大最小值是多少.委椭制从蝎燃片欣乍锦幼锭燎多朽脊咒惹速唉廓戚贰帽带铬引凡班翟谷汰动态规划专题讲义ppt课件动态规划专题讲义ppt课件游游戏戏|这一题作者其实是根
33、据最佳加这一题作者其实是根据最佳加法表达式改编的法表达式改编的.但是他加了一但是他加了一个在圈上的条件个在圈上的条件,怎么办呢怎么办呢?寻找定量!忻斤那柿埠秒靶由轧启缕奎娜馈绿妖渴杨兽抒或沿们废镶榷翌似帜缉稗淤动态规划专题讲义ppt课件动态规划专题讲义ppt课件游游戏戏|可想而知可想而知,因为至少要分成因为至少要分成1堆堆,那那么至少有两个石子之间是会被分隔么至少有两个石子之间是会被分隔开的开的.这就是定量这就是定量!当划分数当划分数1时时,一定有两个相邻石子被划分到不同一定有两个相邻石子被划分到不同的堆里去的堆里去!|于是这个圈被这样的理解断成了一于是这个圈被这样的理解断成了一条线条线,解法
34、就和最佳加法表达式一解法就和最佳加法表达式一样了样了.|当然这个断开的位置是需要枚举的当然这个断开的位置是需要枚举的,然后保留下一个最优值然后保留下一个最优值.显然这个显然这个断开的操作对整个过程没有影响断开的操作对整个过程没有影响,因为这是必然的情况因为这是必然的情况,这是定量这是定量!列乐圣虾金蓉旗毛滚搁奄凑问一街疼椎洱鬃宴月英辅驯哟雪联晤狂械赶砧动态规划专题讲义ppt课件动态规划专题讲义ppt课件最最优优三三角角形形划划分分|问题描述问题描述|给定一具有给定一具有N N（N50N50）个顶点）个顶点( (从从1 1到到N N编号）的凸多边形，每个顶编号）的凸多边形，每个顶点的权均已知。问
35、如何把这个凸点的权均已知。问如何把这个凸多边形划分成多边形划分成N-2N-2个互不相交的个互不相交的三角形，使得这些三角形顶点的三角形，使得这些三角形顶点的权的乘积之和最小？权的乘积之和最小？ 谍壤尚篡程椅泰洁揉楷疼敷吕钱汹湃拉佣孪排车褒辜唇沫纫错币绣医渣刑动态规划专题讲义ppt课件动态规划专题讲义ppt课件最最优优三三角角形形划划分分|这一题大概搜都是十分麻烦的这一题大概搜都是十分麻烦的,可是可是这一题这一题Dp的话的话,比搜索要容易实现和比搜索要容易实现和容易理解得多容易理解得多.|先得表示一下状态先得表示一下状态,我们用我们用fi,j表示表示以第以第i个点开头个点开头,顺时针长度为顺时针
36、长度为j的一的一块子多边形块子多边形.如上图中如上图中f1,5表示的子表示的子多边形多边形(黑色虚线划开黑色虚线划开)允仓脯斧叠毕瘸杀富舌埃稼陈犁啥矛涝察拐撑瘴揩显再斥耻蒋卖邓买怂闽动态规划专题讲义ppt课件动态规划专题讲义ppt课件最最优优三三角角形形划划分分|如果没有红色虚线的部分如果没有红色虚线的部分,或许你或许你会认为决策应该是枚举子多边形内会认为决策应该是枚举子多边形内的两点连线的两点连线,然后分成两个子多边然后分成两个子多边形形.这显然是不行的这显然是不行的,因为计算机已因为计算机已经无法再表示分割出来的子多边形经无法再表示分割出来的子多边形了了(不能用不能用fi,j来表示了来表示
37、了).坪虐塞簇脚封棱寻砧蛋享适迢唾佑粗沂女括贿叙徘鲸菏绊捌鼻告签裸剐天动态规划专题讲义ppt课件动态规划专题讲义ppt课件最最优优三三角角形形划划分分|那么我们该如何决策呢那么我们该如何决策呢?寻找定量寻找定量!|显然可以发现显然可以发现,fi,j表示的子多边表示的子多边形有一条边是在内部的形有一条边是在内部的(黑色虚线黑色虚线),而这一条边在该子多边形内必定属于而这一条边在该子多边形内必定属于某个三角形某个三角形,因为我们选择了该子多因为我们选择了该子多边形作为一种状态边形作为一种状态,那么就一定存在那么就一定存在那条虚线黑边那条虚线黑边,所以一定存在所说的所以一定存在所说的三角形三角形.于
38、是我们枚举这个三角形的于是我们枚举这个三角形的另外一个点在子多边形的位置另外一个点在子多边形的位置,则可则可以把子问题还原到原问题以把子问题还原到原问题(因为该三因为该三角形把多边形划成了两个可以用表示角形把多边形划成了两个可以用表示的多边形和一个三角形的多边形和一个三角形).这些再次分这些再次分割出的子多边形就是以前状态割出的子多边形就是以前状态,而刚而刚才的多边形则是当前状态才的多边形则是当前状态.镊厂碉辙父鸵纱言另束叼细巢碎车送姿球琉霉褪俩励棍慎馏姓梧叼佐侗讫动态规划专题讲义ppt课件动态规划专题讲义ppt课件定定量量|其实定量的作用就是为了写出其实定量的作用就是为了写出状态转移方程状态
39、转移方程,即让人能迅速找即让人能迅速找出状态之间的关系出状态之间的关系(决策决策).通过通过定量的处理定量的处理,当前状态又回到了当前状态又回到了以前状态以前状态,选手就可以知道选手就可以知道,这这一题就是要用动态规划来求解一题就是要用动态规划来求解了了.慧旋躲勿挛靳还驰驶铅匿盘闺啪蓉谰靛电汉唤舶沼补吕梆产暂恢沉蚊妒跪动态规划专题讲义ppt课件动态规划专题讲义ppt课件定定量量|我们来看看刚才的一些题目的定量我们来看看刚才的一些题目的定量.|交错匹配交错匹配:一定存在最后一组交错一定存在最后一组交错(这好像是废话这好像是废话),所以枚举这个最所以枚举这个最后的交错的位置作为状态后的交错的位置作
40、为状态,这样就这样就回到以前状态回到以前状态.|买车票买车票:定量定量1:一定有最后一个车站一定有最后一个车站(这个作为状态这个作为状态);定量定量2:某个车站一某个车站一定是由某个前面的车站到达的定是由某个前面的车站到达的.(导导弹拦截也是这样弹拦截也是这样)|数字三角形数字三角形:某个点一定是由他上某个点一定是由他上面的相邻两点到达的面的相邻两点到达的.(过河卒也是过河卒也是这样这样)定量很不错啊!菠性道九凹懊晓傈酱缄磐课琳述啮第咋茫流膏眠遮慎熄贞柄邓截煽匙仕药动态规划专题讲义ppt课件动态规划专题讲义ppt课件动动态态规规划划的的武武器器|在动规的操作过程中在动规的操作过程中,或者是操或
41、者是操作过程前作过程前,有一些很常用的武器有一些很常用的武器,这里简要介绍两种这里简要介绍两种:珠钝做鲤瞒费孽烁嗽兜魏叔棱踩产踢固岂鞭宰河崖船甜上烟矽贬瓷富育涎动态规划专题讲义ppt课件动态规划专题讲义ppt课件排排序序|武器一武器一:排序排序|遇到过很多需要排序的动态规遇到过很多需要排序的动态规划题目划题目,如果不排序如果不排序,动规的思动规的思想很难体现想很难体现.赚卧荡瞄持乓秉伪威庙扭弓览真缕疯柴乡涎簇缨吉晨袒兵虐箩名盂奠荤监动态规划专题讲义ppt课件动态规划专题讲义ppt课件T To om m的的烦烦恼恼|Tom的烦恼的烦恼 这是大家熟知的一题这是大家熟知的一题,如果不如果不排序的话排
42、序的话,复杂度便是复杂度便是N2,按按起始时间排序复杂度也是起始时间排序复杂度也是N2,二按结束时间排序之后复杂度二按结束时间排序之后复杂度降为了降为了NlogN.费亥筋袱勺值良燃椎现春越硫挖淋嘶谓顿疫念浑斜钻诡绪贿复盔赛韧迟恰动态规划专题讲义ppt课件动态规划专题讲义ppt课件巴巴比比伦伦塔塔|巴比伦塔巴比伦塔|问题描述问题描述: 有很多的不同种类的立方体有很多的不同种类的立方体(长长宽高不同宽高不同),每一类有无限多个每一类有无限多个.将他们一层层的叠加起来将他们一层层的叠加起来,要求要求上面的一块立方体的下底面一定上面的一块立方体的下底面一定要比下面的一块立方体的上底面要比下面的一块立方
43、体的上底面要小要小,就是长和宽都要小于就是长和宽都要小于.问最问最多能建成多高的塔多能建成多高的塔.筷鲁盯慷吁账坍暴容搜窑寄匡野拷棘诬炭乙矗偶赫危圭钎奋搽辛篓欣抖邑动态规划专题讲义ppt课件动态规划专题讲义ppt课件巴巴比比伦伦塔塔|经过研究可以发现经过研究可以发现,每一种类的立方每一种类的立方体有体有3种不同的摆放方式种不同的摆放方式,而每种摆而每种摆放方式最多用放方式最多用1次次,所以可以分离出所以可以分离出3*N块块“不同不同”的立方体的立方体,接下来接下来,或许你仍然不知道如何动规或许你仍然不知道如何动规,那么就那么就试试排序试试排序.列出所有的石块的所有摆列出所有的石块的所有摆放方式
44、放方式xi,yi,zi.xi,yi,zi.必须全部保证必须全部保证xiyixiyi.xiyi.然后按关键字然后按关键字xi,yi,zixi,yi,zi的大小顺序排序的大小顺序排序. .这样就可这样就可以进行十分简单的类似与导弹拦截以进行十分简单的类似与导弹拦截的一个动态规划的处理了的一个动态规划的处理了. .限制条件限制条件是是xixi和和yi,yi,代价值是代价值是zi(zi(高度高度).).舆庐怠辆铁焕铃假肾弦剑吃远绑堡歪奉豢惊隧曼崭驭抿盛驯效黍趋滚爸亨动态规划专题讲义ppt课件动态规划专题讲义ppt课件滑滑雪雪|滑雪滑雪(上海上海2002)|题目的大意是给出一个矩阵题目的大意是给出一个矩
45、阵,如如:对于所给出的矩阵找出一条最长的递减链,满足链中相邻的两个元素间都是在矩阵中相邻的.上图中所给出的矩阵中的最长链是1 2 3 425.琼栓冷釜培肿午陕泉强脆阐涯殃涕铱玲柱蒋津穴茨卸清绿挺梢瞒湾亥沂胯动态规划专题讲义ppt课件动态规划专题讲义ppt课件滑滑雪雪|对于有给出的数字进行递减排对于有给出的数字进行递减排序序,然后两重循环就搞定问题然后两重循环就搞定问题.动态转移方程是动态转移方程是: Fi:=max(Fi,Fj+1); 满足条件是满足条件是i与与j在原矩阵中相在原矩阵中相邻邻.|试想试想,如果你不知道要排序如果你不知道要排序,你你能想到这题是用动态规划吗能想到这题是用动态规划吗
46、?休胆厢笔香磨漆蒂犀挤表琐袱肛曰茁肆票承贞良葫比茎寝圭疮獭侄溢檬畔动态规划专题讲义ppt课件动态规划专题讲义ppt课件填填鸭鸭|武器二武器二:填鸭填鸭|这个思想带有枚举的感觉这个思想带有枚举的感觉.就是就是开个大数组开个大数组,把代价值一个个填把代价值一个个填进去进去.态镜贷募吩戌沛屿睡追备阂芍蛤沙箕烷滚伯哲碟亲钧露溅部良绿绎钦屋数动态规划专题讲义ppt课件动态规划专题讲义ppt课件硬硬币币问问题题|硬币问题（经典问题）硬币问题（经典问题） 就是给出就是给出n种硬币的面值种硬币的面值,问面值问面值 M有多少种不同的表示方法有多少种不同的表示方法. 动态转移方程是动态转移方程是Fi:=Fi+FI
47、-costj.当前状态是当前状态是i,以前状态是以前状态是i-costj.|多米诺骨牌（某题的简化）多米诺骨牌（某题的简化） 有有N张多米诺骨牌张多米诺骨牌,每张的两端有两每张的两端有两个数字个数字,范围在范围在1.6之间之间.每张骨牌可每张骨牌可以正放以正放,也可以反放也可以反放.求出一种摆放求出一种摆放的情况的情况,使得所有的骨牌上端数字之使得所有的骨牌上端数字之和与下端数字之和的差值最小和与下端数字之和的差值最小.求出求出最小差值最小差值.轨拌凝陀孤川枢愤滁抛迭扑艰钡泼酉钾皆帚搪加敞菲喜树麻揣液拐骆沼竹动态规划专题讲义ppt课件动态规划专题讲义ppt课件多多米米诺诺骨骨牌牌可以这么考虑这
48、个问题可以这么考虑这个问题:我们把每一个骨牌的上下差值记我们把每一个骨牌的上下差值记下。接下来的任务便是将这些值下。接下来的任务便是将这些值分成两组，使得他们的和的差值分成两组，使得他们的和的差值最小。动规过程如下：最小。动规过程如下：f0:=true; for i:=1 to n do for j:=sum downto ai do fj:=fj or fj-ai;Sum表示所有差值的和表示所有差值的和. ai表示第表示第i块骨块骨牌牌的差值的差值. J是当前状态是当前状态,j-ai是以前状态是以前状态.fj表示表示j这个差值能否通过组合得到。这个差值能否通过组合得到。接下来的程序就不用我多
49、说了。接下来的程序就不用我多说了。论唯杰唐喊贺油忽烛戚垣痉艇磺过篱品日蠕眩甫您瞎块辉围拙章河交浇岛动态规划专题讲义ppt课件动态规划专题讲义ppt课件商商店店购购物物|商店购物商店购物(IOI)(IOI) 这一题更是需要开一个五维这一题更是需要开一个五维boolbool型数组型数组. .还需要通过递归还需要通过递归求出组合形式求出组合形式. .动规的方程我动规的方程我就不写了就不写了. .拖拜毅桓耙琉乔镣艘粹嘎戏桓绩空琐愿讣规灾阂彼营勿绸褥肥才岁聚来姨动态规划专题讲义ppt课件动态规划专题讲义ppt课件动动态态规规划划的的武武器器|讲完了比较实用的两种种动规的武器之后,我们来看看一些大家可能不
50、太会做的动规类型辐硝弊堤居幽钵砂碍优挎打觉药烷雏期怎彤犯呛核翼靴蔬报坟氖绪怒踏妥动态规划专题讲义ppt课件动态规划专题讲义ppt课件特特殊殊的的动动规规|这里我讲讲三种特殊的动态规这里我讲讲三种特殊的动态规划划:图状动规图状动规,树状动规树状动规,二次动二次动规规.镀龄哪徘棕或抨岩呜宙硬峦王楷雄埃像路猫浦观盅锻拆弥效铆更怔棕着悄动态规划专题讲义ppt课件动态规划专题讲义ppt课件图图状状动动规规|城堡城堡|某国聪明美丽的公主要找一位如意某国聪明美丽的公主要找一位如意郎君，她希望未来的夫君是一个聪郎君，她希望未来的夫君是一个聪明善良，节俭但又不吝啬的人。为明善良，节俭但又不吝啬的人。为了找到理想
51、的人选，她的爸爸了找到理想的人选，她的爸爸国国王，给她修建了一座城堡，这个城王，给她修建了一座城堡，这个城堡有很多房间，房间之间有走廊连堡有很多房间，房间之间有走廊连接，但每进入一个房间必须要花费接，但每进入一个房间必须要花费一定数量的钱币，公主就在某个房一定数量的钱币，公主就在某个房间中等待。开始，国王给每个候选间中等待。开始，国王给每个候选人一样多的钱币，候选人从同一个人一样多的钱币，候选人从同一个地点出发，直到找到美丽的公主为地点出发，直到找到美丽的公主为止，如果这时哪个人找到了公主，止，如果这时哪个人找到了公主，并且钱币刚好用完，那么他将会赢并且钱币刚好用完，那么他将会赢得公主的芳心。
52、得公主的芳心。颗变忘饱肖曰泰蚂透暗档丫策氢汉里达黑久韧旦挡炼广奥杉侠钒沏骚坷显动态规划专题讲义ppt课件动态规划专题讲义ppt课件城城堡堡|乍看此题乍看此题,似乎就是搜没得说了似乎就是搜没得说了,是吗是吗?|如果告诉你这一题是动态规划如果告诉你这一题是动态规划的话的话,你会怎么做你会怎么做?状态是什状态是什么动态转移方程是什么么动态转移方程是什么?权扼佯履捎肠侈羽馏索色搽嫂草逃踌甲坡擦爷怨史弓蝉徐裳神孕懊圭响湿动态规划专题讲义ppt课件动态规划专题讲义ppt课件城城堡堡|既然是问我们能不能到达既然是问我们能不能到达,所以所以想想就应该知道想想就应该知道,动规的数组是动规的数组是bool型的型的
53、.一开始时一开始时,只有出发的只有出发的房间记为房间记为true.|但是但是,并不是以每个房间作为状并不是以每个房间作为状态态,因为还存在一个把钱用光的因为还存在一个把钱用光的问题问题.到达同一个房间时到达同一个房间时,如果如果剩余的钱不一样剩余的钱不一样,也就会有不同也就会有不同的决策的决策.|所以状态就是在剩余所以状态就是在剩余j个钱币的个钱币的时候能否到达第时候能否到达第i个房间个房间.用用fi,j来表示来表示.禄涡秤惟霸芭马判鞍婿哉短衰姐船京日宵空谢庇莫蜒贝绣哇租肤醇绚抚拄动态规划专题讲义ppt课件动态规划专题讲义ppt课件图图状状动动规规于是动态转移方程也就出来了于是动态转移方程也就
54、出来了K表示的是和I连接的一个房间,ci表示进入I号房间的花费.脉惺跺榴周犀罗罢岔璃汀宵刺稠去耪赔柞啄峪贡凑夏庄渣馋绒阉碉坚售滚动态规划专题讲义ppt课件动态规划专题讲义ppt课件树树状状动动规规|没有上司的晚会没有上司的晚会|某公司要举办一次晚会，但是某公司要举办一次晚会，但是为了使得晚会的气氛更加活跃，为了使得晚会的气氛更加活跃，每个参加晚会的人都不希望在每个参加晚会的人都不希望在晚会中见到他的上司，要不然晚会中见到他的上司，要不然他们会很扫兴。现在已知每个他们会很扫兴。现在已知每个人的活跃指数和上司关系（当人的活跃指数和上司关系（当然不可能存在环），求邀请哪然不可能存在环），求邀请哪些人
55、来能使得晚会的总活跃指些人来能使得晚会的总活跃指数最大。数最大。 裙策劫贬逼酶国几延筛喧胚晌加厨秋弊贼琅捏怒暴甥妄涉纤狭七唐帮夹仟动态规划专题讲义ppt课件动态规划专题讲义ppt课件没没有有上上司司的的晚晚会会|按照要求构建一张关系图，可按照要求构建一张关系图，可见这是一棵树。对于这类最值见这是一棵树。对于这类最值问题，向来是用动态规划求解问题，向来是用动态规划求解的。的。|任何一个点的取舍可以看作一任何一个点的取舍可以看作一种决策，那么状态就是在某个种决策，那么状态就是在某个点取的时候或者不取的时候，点取的时候或者不取的时候，以他为跟的子树能有的最大活以他为跟的子树能有的最大活跃总值。分别可
56、以用跃总值。分别可以用fi,1和和fi,0表示。表示。修篙采咽扮锑蕴贬途月惮册胺贰踞疲霹糊桐沾恿粒婶喂玖除欠肘怯身吼忱动态规划专题讲义ppt课件动态规划专题讲义ppt课件没没有有上上司司的的晚晚会会|当这个点取的时候，他的所有当这个点取的时候，他的所有儿子都不能取，所以儿子都不能取，所以fi,1:=sum(fj,0,j为为i的儿子的儿子)i的权值。的权值。|不取的时候，他的所有儿子取不取的时候，他的所有儿子取不取无所谓，不过当然应该取不取无所谓，不过当然应该取价值最大的一种情况。所以价值最大的一种情况。所以fi,0:=sum(max(fj,1,fj,0),j为为i的的i儿子）。儿子）。|这就是
57、树状动规的基本形态。这就是树状动规的基本形态。粪迭伐辙库码耍杯明桑秦良子看卢芝韩饮完部郎弱席爸孟祭弗拓桂踪输饭动态规划专题讲义ppt课件动态规划专题讲义ppt课件二二次次动动规规|在动规的基础上再进行动规，就叫在动规的基础上再进行动规，就叫做二次动规。做二次动规。|买票买票|有一座有一座n层的楼房，某个人要到第层的楼房，某个人要到第n层的任何一个房间买票。每层楼都层的任何一个房间买票。每层楼都有有m个房间。而如果要到第个房间。而如果要到第i层的第层的第j个房间买票，那么必须先在第个房间买票，那么必须先在第i-1层层的第的第j个房间买票或者在第个房间买票或者在第i层的与这层的与这个房间相邻的房间
58、买过票才行个房间相邻的房间买过票才行.而每而每个房间所要收取的票费是不同的个房间所要收取的票费是不同的,给给定每个房间内买票需要的费用定每个房间内买票需要的费用,问要问要在第在第n层的任意一间房间内买到票的层的任意一间房间内买到票的最小消费是多少最小消费是多少.腿淖珐裤揖劝仔念祁厅雄训竟条先梳沽堵缮科弛卖磷蠕蒋筹状卢墙个鞠陨动态规划专题讲义ppt课件动态规划专题讲义ppt课件买买票票|显然不能写这样的状态转移方程显然不能写这样的状态转移方程:fi,j:=min(fi-1,j,fi,j-1,fi,j+1)+wj.因为无法有一种处理顺序因为无法有一种处理顺序使得在使得在fi,j之前同时求得之前同时
59、求得fi,j-1和和fi,j+1的最优值的最优值.|所以动规分两次进行所以动规分两次进行.第一次用状态转移第一次用状态转移方程方程fi,j:=min(fi,j-1,fi-1,j)+wi求出一求出一个不一定是最优的解个不一定是最优的解.再用再用fi,j:=min(fi,j,fi,j+1,j from m-1 downto 1)+wi求出最终的最优解求出最终的最优解,可以证可以证明这样的能够求出真正的最优解明这样的能够求出真正的最优解.|要注意的是这两次动规不能分开做要注意的是这两次动规不能分开做,而要而要在处理每一层的时候都要做在处理每一层的时候都要做,要不然显然要不然显然无法求得最优值。无法求
60、得最优值。束暂景番量页爹想漱戚筋刷樱慰肝辟踏瓜墅桨蛀类焦宗娜耗展愁辊瘟莉愈动态规划专题讲义ppt课件动态规划专题讲义ppt课件综综合合题题|网络（网络（Ural1056,求树的中心）求树的中心）|题目大意是：题目大意是：有一棵有有一棵有N个结个结点的树，给出每个结点的父亲点的树，给出每个结点的父亲（即给出这棵树），边的权都（即给出这棵树），边的权都是是1。每个结点延树的边可以。每个结点延树的边可以走到树的任意一个结点，令走到树的任意一个结点，令Ai为第为第i个结点最远能走的距离，个结点最远能走的距离，求出求出Ai最小的结点有哪些。如最小的结点有哪些。如有多个最小的有多个最小的Ai，则都要输出。
61、，则都要输出。这里这里N=10000N=10000 口丘惑胸眶凶驹肋哎蔫刊侧粹括峰怒韶雏麦毒脆甥悄孝兆应蠕刀砌拓骆肋动态规划专题讲义ppt课件动态规划专题讲义ppt课件网网络络|枚举每个点，然后枚举每个点，然后DFS复杂度复杂度O(N2)，超时是显然的事情。，超时是显然的事情。|可以发现其实有很多可以发现其实有很多DFS都重复做都重复做了同样的工作，产生了浪费，所以了同样的工作，产生了浪费，所以应该选择动态规划解决这个问题。应该选择动态规划解决这个问题。|树上的动规，是否直接可以写出下树上的动规，是否直接可以写出下面的状态转移方城呢？面的状态转移方城呢？|fi:=max(fson,ffathe
62、r)+1 |废话，显然是不行的，废话，显然是不行的，son和和father的值不可能同时得到。的值不可能同时得到。|但是不要放弃，解决这个冲突的方但是不要放弃，解决这个冲突的方法，就是采用二次动规。法，就是采用二次动规。结贞率翻哟摄末虫悠蒂椅镍埋勒嫡涯狐撒粒莆跨肚橙烫小帅琼序贰假避拙动态规划专题讲义ppt课件动态规划专题讲义ppt课件网网络络|第一次动规做第一次动规做fi:=max(fson)+1，第二次动规做第二次动规做fi:=max(fi,ffather + 1) 。|但是存在一个问题就是如果但是存在一个问题就是如果ffather的值是从的值是从i那里得到的，这那里得到的，这样计算显然就错
63、了。样计算显然就错了。|不要放弃，在实际操作过程中，不要放弃，在实际操作过程中，f需需要记下两个值，一个是最优值，一要记下两个值，一个是最优值，一个是次优值，这两个值必须由不用个是次优值，这两个值必须由不用的子结点得到。这样当最优值发生的子结点得到。这样当最优值发生矛盾的时候，次优值一定不会矛盾。矛盾的时候，次优值一定不会矛盾。问题就解决了。复杂度问题就解决了。复杂度O(N)O(N)十分的十分的理想。理想。 竟略貌或堰釜缉窑爹彤议纤舵蜕铁伶晤鳖职踪田锅倾譬痘陋玉沦隆垮买鄂动态规划专题讲义ppt课件动态规划专题讲义ppt课件总总结结|动态规划有很多东西还需要我们动态规划有很多东西还需要我们更加努
64、力地去探索和学习更加努力地去探索和学习.总体总体上说来上说来,动态规划是个既简单又动态规划是个既简单又不简单的算法不简单的算法,熟练地掌握了动熟练地掌握了动态规划态规划,也就熟练地控制了比赛也就熟练地控制了比赛.岩绽樊锅稍玲悸讲锰仔拄屯奉撬炕鼎首饶渡生揉奋澳沉涟爹咐涅咸睹抨帕动态规划专题讲义ppt课件动态规划专题讲义ppt课件锁涤烫棋挥持咀豌殖不便拷猿冀湖茸旋甩吗夜氦驰傅杖诲险频座蓬尚倒录动态规划专题讲义ppt课件动态规划专题讲义ppt课件Thats all!Thank you for listening.少键蓉冶纷倪辕叶啊浓送秉玩娩剔扶厂引廊容含次痞褪幅海移直评刽串醚动态规划专题讲义ppt课
65、件动态规划专题讲义ppt课件动动规规练练习习题题|垃圾陷阱（垃圾陷阱（USACO&TJU1087）|卡门卡门农夫约翰极其珍视的一条农夫约翰极其珍视的一条Holsteins奶牛奶牛已经落了到已经落了到“垃圾垃圾井井”中。中。“垃圾井垃圾井”是农夫们扔垃圾的地是农夫们扔垃圾的地方，它的深度为方，它的深度为D (2 = D = 100)英尺。卡门想把垃圾堆起来，等到堆得与英尺。卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生卡门可以通过吃一些垃圾来维持自己的生命。每个垃圾都可以用来吃或堆放，并且命。每个垃圾都可
66、以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。假设卡门堆放垃圾不用花费卡门的时间。假设卡门预先知道了每个垃圾扔下的时间预先知道了每个垃圾扔下的时间t(0 t = 1000)，以及每个垃圾堆放的高度，以及每个垃圾堆放的高度h(1 = h = 25)和吃进该垃圾能维和吃进该垃圾能维持生命的时间持生命的时间f(1 = f = 30)，要求，要求出卡门最早能逃出井外的时间，假设卡门出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续当前体内有足够持续10小时的能量，如小时的能量，如果卡门果卡门10小时内没有进食，卡门就将饿小时内没有进食，卡门就将饿死。死。 既氮饼噎幂接邀髓主入益哭醋跌收窗萄岂坪膜
67、袁淤菲究惨庸遣徽蔽咨痒蛮动态规划专题讲义ppt课件动态规划专题讲义ppt课件动动规规练练习习题题|字符串距离（字符串距离（TJU1086）|设有字符串设有字符串X，我们称在，我们称在X的头尾及中间插入任意的头尾及中间插入任意多个空格后构成的新字符串为多个空格后构成的新字符串为X的扩展串，如字的扩展串，如字符串符串X为为“abcbcd”，则字符串，则字符串“abcbcd”，“abcbcd”和和“abcbcd”都是都是X的扩的扩展串，这里展串，这里“”代表空格字符。代表空格字符。 如果如果A1是字是字符串符串A的扩展串，的扩展串，B1是字符串是字符串B的扩展串，的扩展串，A1与与B1具有相同的长度
68、，那么我们定义字符串具有相同的长度，那么我们定义字符串A1与与B1的距离为相应位置上的字符的距离总和，而两的距离为相应位置上的字符的距离总和，而两个非空格字符的距离定义为它们的个非空格字符的距离定义为它们的ASCII码的差码的差的绝对值，而空格字符与其它任意字符之间的距的绝对值，而空格字符与其它任意字符之间的距离为已知的定值离为已知的定值K，空格字符与空格字符的距离，空格字符与空格字符的距离为为O。在字符串。在字符串A、B的所有扩展串中，必定存在的所有扩展串中，必定存在两个等长的扩展串两个等长的扩展串A1、B1，使得，使得A1与与B1之间之间的距离达到最小，我们将这一距离定义为字符串的距离达到
69、最小，我们将这一距离定义为字符串A、B的距离。的距离。 请你写一个程序，求出字符串请你写一个程序，求出字符串A、B的距离。的距离。 眶缠糖当脏邢渍罐辉保殉章誓禄中恫弦惹蔫炮揣衬瞄它彩次撑牟帚豪振盖动态规划专题讲义ppt课件动态规划专题讲义ppt课件动动规规练练习习题题|二叉苹果树（二叉苹果树（Ural1018Ural1018）|有一棵苹果树，如果树枝有分叉，一定是有一棵苹果树，如果树枝有分叉，一定是分分2 2叉（就是说没有只有叉（就是说没有只有1 1个儿子的结点）个儿子的结点）这棵树共有这棵树共有N N个结点（叶子点或者树枝分个结点（叶子点或者树枝分叉点），编号为叉点），编号为1-N,1-N,
70、树根编号一定是树根编号一定是1 1。我们用一根树枝两端连接的结点的编号来我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有描述一根树枝的位置。下面是一颗有4 4个个树枝的树树枝的树2 52 5 / / 3 4 3 4 / / 1 1现在这颗树枝条太多了，需要剪枝。但是现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留给定需要保留的树枝数量，求出最多能留住多少苹果。住多少苹果。能趟钻涤吧澡粗音宋剐酷撑鄙码玫使厌因卜锥恢罗面撑夷伤射表趴猎韭彪动态规划专题讲义ppt课件动态规划专题讲义ppt课件动动规规练练习习题题|最最
71、长长前前缀缀 IOI96&USACO 1.4.3）|在生物学中，一些生物的在生物学中，一些生物的结结构是用包含其构是用包含其要素的大写字母序列来表示的。生物学家要素的大写字母序列来表示的。生物学家对对于把于把长长的序列分解成的序列分解成较较短的（称之短的（称之为为元元素的）序列很感素的）序列很感兴兴趣。如果一个集合趣。如果一个集合 P 中的元素可以通中的元素可以通过过串串联组联组成一个序列成一个序列 S ，那么我，那么我们认为们认为序列序列 S 可以分解可以分解为为 P 中中的元素。并不是所有的元素都必的元素。并不是所有的元素都必须须出出现现。举举个例子，序列个例子，序列 ABABACABAA
72、B 可以可以分解分解为为下面集合中的元素：下面集合中的元素： A, AB, BA, CA, BBC 序列序列 S 的前面的前面 K 个字符称作个字符称作 S 中中长长度度为为 K 的前的前缀缀。设计设计一个程序，一个程序，输输入一个元素集合以及一个大写字母序列，入一个元素集合以及一个大写字母序列，计计算算这这个序列最个序列最长长的前的前缀缀的的长长度。度。 屋匀她咽谬疙甘约晶宅频森师芥兴银裴宇羞蓑懦州么醛喇芳厉冈半屋湿嗓动态规划专题讲义ppt课件动态规划专题讲义ppt课件动动规规练练习习题题|祝福（祝福（TJU1078）|得知得知Atlantis即将沉没的消息以后，即将沉没的消息以后，King
73、决定决定把他的人民送到安全的国外去。但是码头已经废把他的人民送到安全的国外去。但是码头已经废弃很多很多年了。码头前有一个迷宫，国王的骑弃很多很多年了。码头前有一个迷宫，国王的骑士只身闯入了这个迷宫士只身闯入了这个迷宫 骑士在迷宫的出口遇骑士在迷宫的出口遇到了不明生物的袭击！骑士因为是单独作战，所到了不明生物的袭击！骑士因为是单独作战，所以很快便招架不住了，他的大马被打得奄奄一息以很快便招架不住了，他的大马被打得奄奄一息（。）这个时候，迷宫中的两座石像（。）这个时候，迷宫中的两座石像(一个是一个是猫老大，一个是天使。（！猫老大，一个是天使。（！)里放出了里放出了无数锋利的刀片，把不明生物全部杀死
74、，骑士当无数锋利的刀片，把不明生物全部杀死，骑士当场晕倒在地。等他醒来，发现马已经死了，手上场晕倒在地。等他醒来，发现马已经死了，手上多了一个戒指，上面写着：多了一个戒指，上面写着： “这个戒指会帮助你这个戒指会帮助你逃脱。它赋予了神奇的力量。有了它，每次移动逃脱。它赋予了神奇的力量。有了它，每次移动如果是只要如果是只要|x-x1|+|y-y1| (x1, y1)的移动！的移动！”(Angel暗自想：还暗自想：还有这么心黑的有这么心黑的)迷宫为迷宫为n*m的矩阵。骑士从的矩阵。骑士从(n, m)到到(1, 1)。问：在戒指的帮助下，骑士最。问：在戒指的帮助下，骑士最少要多少步才能回到入口？在步数最少的前提下，少要多少步才能回到入口？在步数最少的前提下，总共有多少种办法到达入口？注意，骑士不会傻总共有多少种办法到达入口？注意，骑士不会傻到一直停留在原地不动。到一直停留在原地不动。 虐芯鲤糕孔渝谊落割赢损且羹效户庚束菠钎源疾隐恢斯惫埂本横萍城杯览动态规划专题讲义ppt课件动态规划专题讲义ppt课件
