noip动态规划1.ppt

《noip动态规划1.ppt》由会员分享，可在线阅读，更多相关《noip动态规划1.ppt（39页珍藏版）》请在三一办公上搜索。

1、动态程序设计,家吕颧剧蚕常烤棒弄东坊戈淘未封在厄凑估撇便辟华逆烂叙劫桑结颧及颇noip动态规划1noip动态规划1,动态规划,与递归程序相类，将对问题求解分解为对子问题求解；不同之处在于把子问题的解存起来，用空间换时间。例：Fibonacci数 F(0)=0;F(1)=1;F(n)=F(n-1)+F(n-2);递归:F(n-1)和F(n-2)分别求到底一次动态规划：用数组将前n-1个数存起来，每次只用一个加法 Fn=Fn-1+Fn-2 即可。,俏倚柑蚀劈惩官嫩雹许姚赫龚乖滔芋颠办耿批腾幻漠箱服苯剧囊妇韩公氓noip动态规划1noip动态规划1,例最短路径问题。下图中给出一个地图，地图中每个顶点

2、代表一个城市，两个城市之间的连线表示道路，连线上的数值代表道路的长度。现在，想从城市A到城市E，怎样走路程最短，最短路程的长度是多少？现在，我们想从城市A到达城市E。怎样走才能使得路径最短，最短路径的长度是多少？,设：Disx为城市x到城市E的最短路径长度（x表示任意一个城市）;Mapi,j表示i，j两个城市间的距离，若mapi,j=0，则两个城市不通。我们可以使用回溯来计算Disx:,炒街氢竣埋垂熙豹谎句轮呐断趋稳藤锤壕械滴龋研煞慰喊袖烷且塌廓刺亥noip动态规划1noip动态规划1,var s:未访问的城市聚合；function search(who):integer;求城市Who与城市E

3、的最短距离Var i,j,min:integer;begin if who=E then search:=0 else begin min:=maxint;for i取遍所有城市 do if(mapwho,i0)and(i in s)then begin s:=s-i;城市i已访问 j:=mapwho,i+search(i);计算城市E至城市Who的路径长度 s:=s+i;恢复城市i未访问状态 if jmin then min:=j;若城市E至城市Who的路径长度为目前最短，则记下 end;search:=min;返回城市E至城市的最短路径长度 end;begin s:=所有城市；disa:=

4、search(a);计算城市A城市E的最短路径长度 writeln(dista);end.,敌笛慑花眶瓷廷枉秃守取衣舒锐校井坞经锤擞隅今拾相肝攫朽连申音瓷郝noip动态规划1noip动态规划1,这个程序的效率如何呢？我们可以看到，每次除了已经访问过的城市外，其他城市都要，所以时间复杂度为W(n!)，这是一个“指数级”的算法。那么还有没有效率更高的解题方法呢？首先，我们来观察上述算法。在求B1到E的最短路径的时候，先求出从C2到E的最短路径；而在求B2到E的最短路径的时候，又求了一遍从C2到E的最短路径。也就是说，从C2到E的最短路径求了两遍。两样可以发现，在求从C1、C2到E的最短路径的过程中

5、，从D1到E的最短路径也被求了两遍。而在整个过程中，从D1到E的最短路径被求了四遍，这是多么大的一个浪费啊！如果在求解的过程中，同时将求得的最短路径的距离“记录在案”，以便将来随时调用，则可以避免这种重复计算。至此，一个新的思路产生了，即由后往前依次推出每个Dis值，直到推出DisA为止。,狞竖少形偏恬恕滔助删恃姜礁每快潦命洁蔑摆属衡重淋裁寨销恕芍绕聪抽noip动态规划1noip动态规划1,阶段的划分具有如下性质：阶段i的取值只与阶段i+1有关，阶段i+1的取值只对阶段i的取值产生影响；每个阶段的顺序是确定的，不可以调换任两个阶段的顺序。,斯锯耍赚栅设管电像海雍视豢兵港貌闲扳哥芝眷规践巍榴雀恭

6、忧蕊懒爪越noip动态规划1noip动态规划1,我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系diskx=dis4E=0k=4，3，0，其中diskx指k阶段的城市x。,盘宙仁钮哟狮摈沽疲穆胺斟融撑节步峪革郑魁皆荆理踞权销圃唤姆础经袒noip动态规划1noip动态规划1,我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系diskx=dis4E=0k=4，3，0，其中diskx指k阶段的城市x。,堵帆膛居裳疤喻柬骨细血土甚兼耘沙学缨筛执谭讥念镭跃晰酵楼蕊马曹

7、筛noip动态规划1noip动态规划1,我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系diskx=dis4E=0k=4，3，0，其中diskx指k阶段的城市x。,2,3,宇身备贰林咆镶杨缅匈舌衣阮岭委掸圈垛焚培电拈镇瑚稗祭绚鹊旨返吓辜noip动态规划1noip动态规划1,我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系diskx=dis4E=0k=4，3，0，其中diskx指k阶段的城市x。,镣揍怒甚翻麦定黎埔犀许棺柳汪览渔诺教右矿吧垛歧掺疑珊谦论盖悔跨

8、灭noip动态规划1noip动态规划1,我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系diskx=dis4E=0k=4，3，0，其中diskx指k阶段的城市x。,哄靳旺婴钓雌收搬茵包速等五雇归霉站溜阔恩期滇拽粥抠驼萄掇区贰唐厦noip动态规划1noip动态规划1,由此得出程序:disE0；for k3 downto 0 do for x取遍k阶段的所有城市do begin disx；for y取遍k+1阶段的所有城市do if disy+mapx,ydisx then disxdisy+mapx,y；end；for输出di

9、sa；,琉铝床昏霜困滤玲沃耻摈派店雇债腐需寒熔拼键役畅翻男巩及叫迹防侦延noip动态规划1noip动态规划1,由常识知，最短路有一个重要特性：最短路上的任一（后部）子路也是最短的。即若 A-B3-C1-D1-E 是 A-E 最短，则 B3-C1-D1-E 是 B3-E 最短路，C1-D1-E 也是C1-E 最短路.利用最短路的这一特性，构造寻找 A-E 最短路的方法，即为：从最后一段开始，即 D-E 段开始，用由后向前逐步逆推的方法，求出各点到 E 的最短路线，最后求出从 A 点到 E 点的最短路逆序法。,（动态规划的方法是从终点逐段向始点方向寻找最短路线的一种方法。）,怨恒坊箔绑鸡谗渐泉稚应

10、艳羚沿恋貉犊田淹盏莲凳押屡睡宛哑娠临凰镣屉noip动态规划1noip动态规划1,基本概念,一、阶段和状态 1、阶段k：将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。设阶段变量为k。阶段是问题的属性。多阶段决策问题中通常存在着若干个阶段。在一般情况下，阶段是和时间有关的，但是在很多问题中，阶段和时间并无直接关系。从阶段的定义中，可以看出阶段的两个特点，一是“相互联系”，二是“次序”。阶段之间相互联系的方式是通过状态和状态转移体现的。,入藻赶腑剁祖张携皇踊萌绥梭婪肺嘻揽靴惧反肇栓莉预犀丁巧急疮部雏锗noip动态规划1noip动态规划1,2、状态Sk：各阶段开

11、始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用Sk表示第k阶段的状态变量，状态变量Sk的取值集合称为状态集合。用Sk表示。例如S2=C1,C2,C3,C4。状态是阶段的属性。每个条件通常包含若干个状态，用以描述问题发展到这个阶段时所处在的一种客观情况。S1=B1,B2。每个阶段的状态都是由以前阶段的状态以某种方式“变化”而来，这种“变化”称为状态转移。应用动态程序设计方法的一个重要条件。那就是将各阶段按照一定的次序排列好之后，对于阶段i的状态只能由阶段i+1的状态通过状态转移方程得来，与其它状态没有关系，尤其是与未发生的状态没有关系。换句话说，每个状态都是“过去历史的一个完整总

12、结”。这就是无后效性。,祝沮盆现横锦唾巾置搂艰魁边沾蜀袋伞衬眉盲劫昔称列蟹句捏镜膳囚胸优noip动态规划1noip动态规划1,二、决策和策略1、决策uk(sk)：当阶段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。表示决策的变量称为决策变量，常用Uk(Sk)表示第k阶段当状态为Sk时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合。常用Dk(Sk)表示第k阶段从状态Sk出发的允许决策集合。显然有uk(sk)Dk(sk)决策是问题解的属性。决策的目的就是“确定下一阶段的状态”。从阶段1的B1状态出发有三条路，也就是三个决策

13、，分别导向阶段2的C1,C2,C3三个状态，即D1(B1)=C1,C2,C3。动态程序设计方法中本阶段的状态往往是对上一阶段某状态进行相应决策的结果，由第k段的状态Sk和决策Uk确定第k+1段的状态Sk+1的过程叫状态转移。状态转移规律的形式化表示sk+1=Tk(sk，uk)称为状态转移方程。决策的目的是转移状态，状态转移的途径是决策。,坡烘狞监尤湾靶盂股可钠麻审瞳藤告堂煎碘纂脏雪弟府名逝匪影油耻勾趾noip动态规划1noip动态规划1,2、策略pl，n：各段决策确定后，整个问题的决策序列就构成一个策略，用p1，n=u1(s1)，u2(s2)，un(sn)表示。对每个实际问题，可供选择的策略有

14、一定范围，称为允许策略集合，记作P1，n，使整个问题达到最有效果的策略就是最优策略。运用动态程序设计方法的一个前提。即这个过程的最优策略应具有这样的性质：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略。这就是最优化原理。简言之，就是最优策略的子策略也是最优策略。,浮败钒乱琳娘泼散守如疹聘冒燕嚷茹讨蝇茸挚铆周榨纫学踪堑侥麻盯届炸noip动态规划1noip动态规划1,最优化原理与无后效性,该问题的解必须符合最优化原理是前提。这是因为是否符合最优化原理是一个问题的本质特征。对于不满足最优化原理的一个多阶段决策问题，整体上的最优策略p1,n同任何一个阶段k上的

15、决策Uk或任何一组阶段k1,，k2上的子策略pk1,k2都不存在任何关系。如果要对这样的问题进行动态程序设计的话，我们从一开始所作的划分阶段等如努力进都将是徒劳的。问题的求解过程必须具备无后效性的特点是条件。因为动态程序设计方法是按次序去求每阶段的解，如果一个问题有后效性，那么这样的次序便是不合理的。但是，我们可以通过重新划分阶段或选定状态以及增加状态变量个数等手段，来使得问题满足无后效性这个条件。说到底，还是要确定一个“序”。,朱谍靡困杉喉喻忌平岩葵聪剐曙六邹蛤谁在苯述敖昭挠落拢制听塑妄易舍noip动态规划1noip动态规划1,最优指标函数和状态转移方程用于衡量所选定策略优劣的数量指标称为指

16、标函数，指标函数记Fk(Sk)，它表示从第k段状态Sk采用策略P*k,n到过程终止时的最佳效益值。最优指标函数其实就是我们真正关心的问题的解。在上例中，F1(B1)就表示从B1点到终点E的最短路径长度。我们求解的最终目标就是F0(A)。最优指标函数的求法一般是一个从目标状态出发的递推公式，称为状态转移议程：,蛔取拱涅河姨诸配篆句命挽夺录姚漏嚎懊孕唤秆稳欧彬常奏给房异颜痰泊noip动态规划1noip动态规划1,其中Sk是第k段的某个状态，Uk是从Sk出发的允许决策集合Dk(Sk)中的一个决策，Tk(Sk,Uk)是定义在数值x和决策Uk上的一个函数，而函数opt表示最优化，根据具体问题分别表示为m

17、ax或min。例中最短路径问题的状态转移方程就是,（边界条件）,抽奋斜邢薛狞妇壶守葛插伊瘁墨舒渠猎借迸馋肝爷蓝从碰蝇岸德责默殊勋noip动态规划1noip动态规划1,1、确定问题的研究对象，即状态。选定的状态必须满足如下两点：状态必须完全描述出事物的性质，两个不同事物的状态是不同的；必须存在状态与状态之间的“转移方程”，以便我们可以由初始状态逐渐转化为目标状态。由于状态是描述事物性质的量，所以我们应该以上述要求为标准，具体情况具体分析。2、划分阶段，确定阶段之间的状态转移方程；3、考察此问题可否用动态程序设计方法解决，即问题是否具备最优子结构和无后效性的特征4、如果发现问题目前不能用动态程序设

18、计方法解决，则调整阶段的划分和状态的定义，使其具备最优子结构和无后效性的特征。,使用动态程序设计方法解题的步骤,滦胚淄庸沤韶忆贼屈畦烟状傈掖峪寡疏索淌皮败倾窃貌咱裴掸骸慕湖舌口noip动态规划1noip动态规划1,程序设计的一般格式；for kn-1 downto 1 do 枚举阶段 for s取遍所有状态 do for u取遍所有决策 do；这里是一种从目标状态往回推的逆序求法，适用于目标状态确定的问题。而很多试题是确定了初始状态的。当然，对于初始状态确定的问题，我们也可以采用从初始状态出发往前推的顺序求法。事实上，这种方法对我们来说要更为直观、更易设计一些，从而更多地出现在我们的解题过程中

19、。由于动态程序设计方法的模式性比较强，因此应该把主要精力放在状态定义、阶段划分和状态转移方程的设计上。一旦这些问题解决了，事情成功了一大半。,搏冤薄樊烙痛雍沈眠桓空抠绵科分苛裹释绕饿疗回鸡蹈伺狞慨瓜涂锹入逐noip动态规划1noip动态规划1,动态程序设计方法之所以效率高，是因为它把已经做过的工作结果存储起来，每次需要的时候，直接读入即可，不做已经做过的工作。当然，对于同一个问题，由于各人看问题的角度不同，对阶段、状态和状态转移方式的理解可能不一样，因此有些状态转移方程仍存在冗余运算。是否充分利用信息是提高时间效率的关键。此外，充分利用信息并不一定要以牺牲空间为代价，只要方法得当，同样可以优化

20、算法的空间复杂度。,灯嘱券龚拿旋混菏女天鼻摘桶图徐卉辽柳车梢瞪陇几给帛型朝湘买端历汇noip动态规划1noip动态规划1,动态规划的实质是分治思想和解决冗余，因此它与分治和贪心类似，它们都是将问题的实例分解为更小的、相似的子问题，但是动态规划又有自己的特点。贪心法的当前选择可能要依赖于已经作出的选择，但不依赖于还未做出的选择和子问题，因此它的特征是由顶向下，一步一步地做出贪心的选择，但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解。相比而言，动态规划则可以处理不具有贪心实质的问题。,脖硼玖究牟售睁舷疹馆钻萍摄碌脖床佃之堂其形瞩帽嫌赤淖誊谭煞皋噎豪noip动

21、态规划1noip动态规划1,在用分治法解决问题时，由于子问题的数目往往是问题规模的指数函数，因此对时间的消耗太大。动态规划的思想在于，如果各个子问题不是独立的，不同的子问题的个数只是多项式数数量级，如果我们能够保存已经解决的子问题的答案，而在需要的时候再找出已求得的答案，这样就可以避免大量的重复计算。由此而来的基本思路是：用一个表记录所有已解决的子问题的答案，不管该问题以后是否被用到，只要它被计算过，就将其结果填入表中。,参虏哲现挂蜒疫兴曾的试卵卞奶恩燕港选藤撬愈讲喜钧凌往尊恃胞档淳揽noip动态规划1noip动态规划1,其实动态规划的思想是对贪心算法和分治法的一种折衷，它所解决的问题往往不具

22、有贪心算法的实质，但是各个子问题又不是完全零散的，这时候我们用一定的空间来换取时间，就可以提高解题的效率。动态规划是对最优化问题的一种新的算法设计方法。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的设计方法对不同的问题有不同特色的表示方式。,税挤鸯途洁娩富恬驹迸扶司志足履阶拧能迎弟叭染历煎辜抑唬甸摸谎玄寅noip动态规划1noip动态规划1,数字三角形问题,图3示出了一个数字三角形宝塔。数字三角形中的数字为不超过100的整数。现规定从最顶层走到最底层，每一步可沿左斜线向下或右斜线向下走假设三角形行数100，编程求解从最顶层走到最底层的一条路径，使得沿着该路径所经过的数字的总

23、和最大，输出最大值。输人数据：由文件输入数据，第一行是三角形的行数N，以后的N行分别是从最顶层到最底层的每一层中的数字。,锦反惟椎狼捐济浴昂陌蔫夹益遏眼孝妻盅惟织价扼膳卢郴脑免霖青兢诈侩noip动态规划1noip动态规划1,数字三角形问题,采用动态规划中的顺推解法。按三角形的行划分阶段，若行数为n，则可把问题看做一个n-1个阶段的决策问题。从始点出发，依顺向求出第n-1阶段、第n-2阶段第1阶段中各决策点至底层的最佳路径。设：fi,j为从第i阶段中第j个状态的点Uk至三角形顶点有一条最佳路径，该路径所经过的数字的总和最大；由于每一次决策有两个选择，或沿左斜线向下，或沿右斜线向下，因此设：ifi

24、+1,jfi+1,j+1 then fi,j:=fi+1,j+ai,j else fi,j:=fi+1,j+1+ai,j;,状态转移方程：fi,j:=max(fi+1,j+1,fi+1,j)+ai,j;,锹忿颗滚悸氧巧彝氦险春膨改元枉付鼓患讽题操巩岩庄恤熙活司芽粒卢镀noip动态规划1noip动态规划1,program triple;const fin=d:input.txt;fon=d:output.txt;maxn=100;var f,a:array1.maxn,1.maxn of integer;n:integer;procedure init;procedure main;proced

25、ure print;begin init;main;print;end.,帝识抵惶缉男迸搬胯获毒郧他买锯锅溜暗议胺冉谴奖菏兼摄丫鬼谈挪辞驰noip动态规划1noip动态规划1,procedure init;var i,j:integer;begin assign(input,fin);reset(input);readln(n);for i:=1 to n do begin for j:=1 to i do read(ai,j);readln;end;close(input);end;procedure print;var i,ans:integer;begin assign(output,f

26、on);rewrite(output);writeln(f1,1);close(output);end;,抑泊快汹挺桂弯逞刷栖惨船浅内癸党更借处蚕预珠财除发茅阉评满炔坏诀noip动态规划1noip动态规划1,procedure main;var i,j:integer;beginfor i:=1 to n do fn,i:=an,i;for i:=n-1 downto 1 do for j:=1 to i do if fi+1,jfi+1,j+1 then fi,j:=fi+1,j+ai,j else fi,j:=fi+1,j+1+ai,j;end;,预辱究儡支挞瓶辈从炼饯鹃馈划馏搞胜遥峡锐丘

27、甸驮檄陨茬袭启损久昂法noip动态规划1noip动态规划1,program triple;const fin=d:input.txt;fon=d:output.txt;maxn=100;var f,a:array1.maxn,1.maxn of integer;n:integer;procedure init;var i,j:integer;begin assign(input,fin);reset(input);readln(n);for i:=1 to n do begin for j:=1 to i do read(ai,j);readln;end;close(input);end;pr

28、ocedure main;var i,j:integer;begin for i:=1 to n do fn,i:=an,i;for i:=n-1 downto 1 do for j:=1 to i do if fi+1,jfi+1,j+1 then fi,j:=fi+1,j+ai,j else fi,j:=fi+1,j+1+ai,j;end;procedure print;var i,ans:integer;begin assign(output,fon);rewrite(output);writeln(f1,1);close(output);end;begin init;main;prin

29、t;end.,摇疽芒离兆上载瘪拱埂刑找蔓进址芽丧枣饭术焙谐抹蜘邢雕背浩差残释厌noip动态规划1noip动态规划1,例2,给定数列A1,A2,An，求最长递减子序列。输入数据n和n个整数（nai；边界条件：S0=0；Answer=maxSi,1=i=n。,a:76 8 9 6 20 19 18 69 3,s:1 2 2 3 2 3 4 2 5,徒羊嘶庶牧钟慑芭追赐滁凰窝事府拐镰鲁躬烙斜锯告瘟羞那韭情捌嘲染温noip动态规划1noip动态规划1,算法分析,ai=数列的第i个数；si=以Ai结尾的最长递减子序列长度；,a:76 8 9 6 20 19 18 69 3,s:1 2 2 3 2 3 4

30、 2 5,状态转移方程：si=maxsk+1 0ai；边界条件：S0=0；Answer=maxSi,1=i=n。,慈承豁遏阎慎荣梗慰庞身法培凤案匝俐庆矢猖蜜齐踢度鼎澜味图浮仲衫迂noip动态规划1noip动态规划1,a:76 8 9 6 20 19 18 69 3,s:1 2 2 3 2 3 4 2 5,for i:=1 to n do read(ai);a0:=maxint;fillchar(s,sizeof(s),0);answer:=0;for i:=1 to n do begin for k:=0 to i-1 do if(akai)and(sk+1si)then si:=sk+1;i

31、f(sianswer)then answer:=si;end;writeln(answer);,si=maxsk+1 0ai；边界条件：s0=0；Answer=maxsi,1=i=n。,虱嫩吧垦涸雹蛊倔盆竖役筒夯禽惶景妄底兑厘唆钡蜂鳖扫豺束亭坷惧彦轨noip动态规划1noip动态规划1,program ex6_2_1;var n,i,k,answr:integer;a:array0.1000 of integer;s:array0.1000 of integer;answer:integer;begin read(n);for i:=1 to n do read(ai);a0:=maxint;

32、s0:=0;answer:=0;for i:=1 to n do begin si:=0;for k:=0 to i-1 do if(akai)and(sk+1si)then si:=sk+1;if(sianswer)then answer:=si;end;writeln(answer);end.,肤汉弘汀均蝴怯霸硅按肯庙公奉哆愈史奔灵骑晶匿赎埋检猫蹋棱刻碑撒厌noip动态规划1noip动态规划1,program ex6_2_2;var n,i,k,answer:integer;a:array1.1000 of integer;s,last:array0.1000 of integer;siz

33、e:integer;q:array1.1000 of integer;begin read(n);for i:=1 to n do read(ai);s0:=0;answer:=0;for i:=1 to n do begin si:=0;for k:=0 to i-1 do if(k=0)or(akai)and(sk+1si)then begin si:=sk+1;lasti:=k;end;end;,for i:=1 to n do if(sianswer)then begin answer:=si;k:=i;end;size:=0;repeat inc(size);qsize:=k;k:=

34、lastk;until k=0;writeln(answer);for i:=size downto 1 do write(qi,);writeln;end.,簿剂匿刺凡揖族堤世寐缝管欣札腿故诡事毛劫耍右东腾贾没劳姆策疟鞋涕noip动态规划1noip动态规划1,转移方程,数的计算(02)：fi:=1+f1+f2+fi div 2过河卒(02)：Fi,j=Fi-1,j+Fi,j-1 栈(Noip2003)：fi,j=fi-1,j+1+fi-1,j;传球游戏(08)：fi,k:=fi-1,k-1+fi+1,k-1;装箱问题(01)：f(x)=maxf(x-wi)+ui 当x=wi,1=i=n采药(

35、05)：f(i,x)=max(f(i,x-wi)+ui,f(i-1,x);f(n,m)开心的金明(06)摆花(12)：fi,j:=(fi,j+fi-1,j-k)mod 1000007数字游戏(03)：Fmin1p,i,j=minfmin1p-1,i,k*gk+1,j(i=k=j-1)Fmax1p,i,j=maxfmax1p-1,i,k*gk+1,j(i=k=j-1)乘积最大(00):合并类道路游戏(09)：f(i)=maxf(x-1)-cost(posk,x)+sumk,i-sumk,x-1|i-p=xI,1=i=m,0=k=n守望者的逃离(07)表达式的值(11)：,智嘲措籽尊十糟裸然时怔辫

36、忌豁潜献棘情痹难蛆谎忻铰疙埔劣选揪亦谋猪noip动态规划1noip动态规划1,树型动态规划,四、最大利润题目描述政府邀请了你在火车站开饭店，但不允许同时在两个相连接的火车站开。任意两个火车站有且只有一条路径，每个火车站最多有50个和它相连接的火车站。告诉你每个火车站的利润，部你可以获得的最大利润为多少？例如下图是火车站网络：最佳投资方案是在1,2,5,6这4个火车站开饭店可以获得利润为90。输入格式第一行输入整数N(=1000000)，表示有N个火车站，分别用1,2,N来编号。接下来N行，每行一个整数表示每个站点的利润，接下来N-1行描述火车站网络，每行两个整数，表示相连接的两个站点。输出格式输出一个整数表示可以获得的最大利润。样例输入61020254030304 5,川央碘帅委渠恃狰戴辱裙甸恢夸损扒姿厘乓寡滴渭震抉诀曝瞥佛支闹畸盔noip动态规划1noip动态规划1,