动态程序设计

《动态程序设计》由会员分享，可在线阅读，更多相关《动态程序设计（69页珍藏版）》请在装配图网上搜索。

1、动态程序设计动态程序设计基本原理1、多阶段最优化决策：、多阶段最优化决策：即由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条最优的活动路线。带权有向的多段图 上一阶段的状态下一阶段的状态决策概念w 状态状态（State）：表示事物的性质，是描述“动态规划”中的“单元”的量。亦是每一阶段求解过程的出发点。w 阶段阶段（Stage）：阶段是一些性质相近，可以同时处理同时处理的状态集合，或者说，阶段只是标识那些处理方法相同、处理顺序无关的状态。w 决策决策（Decision）：每个阶段做出的某种选择性的行动，是程序所需要完成的选择。w

2、状态转移方程：状态转移方程：是前一个阶段的状态转移到后一个的状态的演变规律，是关于两个相邻阶段状态变化的方程，是“动态规划”的中心。设设 fk(i)k阶段状态i的最优权值，即初始状态至状态i的最优代价 fk+1(i)=minxk(j)+u(i,j)基本原理w 最优性原理作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。无后效性原则给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。机器分配 w 总公

3、司拥有高效生产设备M台，准备分给下属的N个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这M台设备才能使国家得到的盈利最大？求出最大盈利值。其中M=15，N=10。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数M。w 数据文件格式为：第一行保存两个数，第一个数是设备台数M，第二个数是分公司数N。接下来是一个M*N的矩阵，表明了第I个公司分配J台机器的盈利。分析w 用机器数来做状态，数组FI，J表示前I个公司分配J台机器的最大盈利。则状态转移方程为:w FI，J=MaxFI-1，K+ValueI，J-K(1=I=N,1=J=M,0=K=J)w 初始值:F

4、(0,0)=0w 时间复杂度O(N*M2)最长不下降序列 w 设有整数序列b1,b2,b3,bm，若存在下标i1i2i3 in，且bi1bi2bi3 bin，则称 b1,b2,b3,bm中有长度为n的不下降序列bi1,bi2,bi3,bin。w 求序列b1,b2,b3,bm中所有长度(n)最大不下降子序列w 输入：整数序列。w 输出：最大长度n和所有长度为n的序列个数。分析（1）设f(i)为前i个数中的最大不下降序列长度,则w f(i)=maxf(j)+1 (1=ji=m,bjbi)w 边界为F(1)=1(2)设t(i)为前i个数中最长不下降序列的个数,则w t(i)=t(j)(1=ji=m,

5、bjbi,f(j)=f(i)-1)w 初始为t(i)=1w 当f(i)=n时，将t(i)累加w 举例：1 2 3 4 6 5 8 10 9 f:1 2 3 4 5 5 6 7 7 t:1 1 1 1 1 1 2 2 2答案：f=7时，边界为t=4进一步(3)求本质不同的最长不下降序列个数有多少个？如：1 2 3 4 6 5 8 10 9 有，1 2 3 4 6 8 10,1 2 3 4 5 8 10,1 2 3 4 6 8 9,1 2 3 4 5 8 9 都是本质不同的。但对于 1 2 2 3 3 5 4 f 1 2 2 3 3 5 4 t 1 1 1 2 2 4 4 答案有8个，其中4个1

6、2 3 5，4个1 2 3 4改进算法w 上例显然对于相两个相同的数，重复算了多次因此，我们对算法进行改进：w 对原序列按b从小到大（当bi=bj时按F从大到小）排序，增设Order(i)记录新序列中的i个数在原序列中的位置。可见，w 求t(i)时，当f(j)=f(j+1),b(j)=b(j+1)且Order(j+1)Order(i)时，便不累加t(j)。这样就避免了重复。w 上述算法的时间复杂度为O(n2)凸多边形三角划分 w 给定一个具有N（N50）个顶点（从1到N编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小

7、？w 输入文件：第一行 顶点数Nw 第二行 N个顶点（从1到N）的权值w 输出格式：最小的和的值w 各三角形组成的方式w 输入示例：5w 121 122 123 245 231 w 输出示例：The minimum is：12214884w The formation of 3 triangle:w 3 4 5,1 5 3,1 2 3 分析w 设FI,J（IJ）表示从顶点I到顶点J的凸多边形三角剖分后所得到的最大乘积，我们可以得到下面的动态转移方程：w FI,J=MinFI,K+FK,J+SI*SJ*SK (0IKJ=N)w 初始条件:F1，2=0w 目标状态:F1,Nw 但我们可以发现,由于

8、这里为乘积之和，在输入数据较大时有可能超过长整形范围，所以还需用高精度计算 系统可靠性 w 一个系统由若干部件串联而成，只要有一个部件故障，系统就不能正常运行，为提高系统的可靠性，每一部件都装有备用件，一旦原部件故障，备用件就自动进入系统。显然备用件越多，系统可靠性越高，但费用也越大，那么在一定总费用限制下，系统的最高可靠性等于多少？w 给定一些系统备用件的单价Ck，以及当用Mk个此备用件时部件的正常工作概率Pk（Mk），总费用上限C。求系统可能的最高可靠性。w 输入文件格式：第一行：n C第二行：C1 P1(0)P1(1)P1(X1)（0=X1=C/Ck）第 n 行：Cn Pn(0)Pn(1

9、)Pn(Xn)（0=Xn=C/Cn）分析w 例：输入：2 20 3 0.6 0.65 0.7 0.75 0.8 0.85 0.9 5 0.7 0.75 0.8 0.8 0.9 0.95 输出：0.6375w 设FI,money表示将money的资金用到前I项备用件中去的最大可靠性，则有w FI,money=maxFI-1,moneyk*CostI w (0=I=n,0=K=money div Cost(I)w 初始：F0,0=0w 目标：Fn,C=0快餐问题 w Peter最近在R市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套餐由A个汉堡，B个薯条和C个饮料组成。价格便宜。为了

10、提高产量，Peter从著名的麦当劳公司引进了N条生产线。所有的生产线都可以生产汉堡，薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡，薯条和饮料的单位生产时间又不同。这使得Peter很为难，不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100个。w 输入:第一行为三个不超过100的正整数A、B、C中间以一个空格分开。第二行为3个不超过100的正整数p1,p2,p3分别为汉堡，薯条和饮料的单位生产耗时。中间以一个空格分开。第三行为N(0=0=10)，第四行为N个不超过10000的正

11、整数，分别为各条生产流水线每天提供的生产时间，中间以一个空格分开。w 输出:每天套餐的最大产量。分析w 本题是一个非常典型的资源分配问题。由于每条生产线的生产是相互独立，不互相影响的，所以此题可以以生产线为阶段用动态规划求解。w 状态表示：用pi,j,k表示前i条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。w 用ri,j,k表示第i条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。w 态转移方程：pi,j,k=Maxpi-1,j1,k1+ri,j-j1,k-k1 (0=j1=j=100,0=k1=k=100,且(j-j1)*p1+(k-k1)*p2=Ti-第i条生产线的

12、生产时间)w ri,j-j1,k-k1=(Ti-(j-j1)*p1+(k-k1)*p2)div p3;w 此算法的时间复杂度为O(N*1004),优化w 在本题中，可以在动态规划方法中加入了贪心算法思想：即首先计算出每天生产套数的上限值（由A,B,C计算，即min100 div A，100 div B，100 div c），接着，用贪心法计算出这N条流水线可以生产的套数，并与上限比较，大于则输出上限值并退出，否则再调用动态规划；同时，在运行动态规划的过程中，也可以每完成一阶段工作便与上限值进行比较，这样以来，便可望在动态规划完成前提前结束程序。其算法设计为：w S1：读入数据。w S2：贪心求

13、上限并计算出一可行解，判断是否需进行下一步。w S3：动态规划求解。w S4：输出。其他优化方法w 1.存储结构：由于每一阶段状态只与上一阶段状态有关，所以我们可以只用两个100*100的数组滚动实现。但考虑到滚动是有大量的赋值，可以改进为动态数组，每次交换时只需交换指针即可，这样比原来数组间赋值要快。w 2.减少循环次数：在计算每一阶段状态过程中无疑要用到4重循环，我们可以这样修改每一重循环的起始值和终数，其中q1,q2为A，B上限值。w 原起始值 改进后的起始值wfor i:=1 to n do for i:=1 to n do wfor j:=0 to toti div p1 do fo

14、r j:=0 to min(q1,toti div p1)dowfor k:=0 to(toti-p1*j)div p2 do for k:=0 to min(q2,(toti-p1*j)div p2)dowfor j1:=0 to j do for j1:=max(0,j-ti div p1)to min(j,toti-1 div p1)dow for k1:=0 to k do for k1:=max(0,k-(ti-(j-j1)*p1)div p2)to min(k,(toti-1-p1*j1)div p2)do 石子合并 w 在一园形操场四周摆放N堆石子(N100),现要将石子有次序地

15、合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(20),(1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少(2)选择一种合并石子的方案,使得做N-1次合并,得分的总和最大w 输入数据:第一行为石子堆数N;第二行为每堆石子数,每两个数之间用一空格分隔.w 输出数据:从第1至第N行为得分最小的合并方案.第N+1行为空行.从N+2到2N+1行是得分最大的合并方案.示例贪心法 N=5 石子数分别为3 4 6 5 4 2。用贪心法的合并过程如下：第一次 3 4 6 5 4 2得分 5第二次 5 4 6 5 4

16、得分9第三次 9 6 5 4得分9第四次 9 6 9得分15第五次 15 9得分24第六次24总分：62然而仔细琢磨后，发现更好的方案：第一次3 4 6 5 4 2得分 7第二次7 6 5 4 2得分13第三次13 5 4 2得分6第四次13 5 6得分11第五次 13 11得分24第六次24总分：61显然，贪心法是错误的。动态规划 w 用datai,j表示将从第i颗石子开始的接下来j颗石子合并所得的分值，w maxi,j表示将从第i颗石子开始的接下来j颗石子合并可能的最大值，那么：w maxi,j=max(maxi,k+maxi+k,j k+datai,k+datai+k,jk)(2=k=j

17、)w maxi,1=0w 同样的，我们用mini,j表示将第从第i颗石子开始的接下来j颗石子合并所得的最小值，可以得到类似的方程：w mini,j=min(mini,k+mini+k,j k+datai,k+datai+k,j k)(0=k=j)w mini,0=0w 这样，我们完美地解决了这道题。时间复杂度也是O(n2)。积木游戏 w 一种积木游戏，游戏者有N块编号依次为1，2，N的长方体积木。第I块积木通过同一顶点三条边的长度分别为ai,bi,ci（i=1,2,N），1 从N块积木中选出若干块，并将他们摞成M（1=M=N）根柱子，编号依次为1,2,M，要求第k根柱子的任意一块积木的编号都必

18、须大于第K-1根柱子任意一块积木的编号（2=K=n），x,y是上面一块积木接触面的两条边（x=y），则一定满足m.=x和n=y；w 下面的积木的编号要小于上面的积木的编号。w 请你编一程序，寻找一种游戏方案，使得所有能摞成的M根柱子的高度之和最大。积木游戏w 输入数据：w 文件的第一行是两个正整数N和M（1=M=N=100）,分别表示积木总数和要求摞成的柱子数。这两个数之间用一个空格符隔开。接下来的N行是编号从1到N个积木的尺寸，每行有三个1至500之间的整数，分别表示该积木三条边的长度。同一行相邻两个数之间用一个空格符隔开。w 输出数据：w 文件只有一行，是一个整数，表示所求得的游戏方案中M

19、根柱子的高度之和 分析w 设（1）fi,j,k表示以第i块积木的第k面为第j根柱子的顶面的最优方案的高度总和；（2）blocki,k 记录每个积木的三条边信息（blocki,4:=blocki,1;blocki,5:=blocki,2）。其中blocki,j+2表示当把第i块积木的第j面朝上时所对应的高，即所增加的高度；（3）cani,k,p,kc表示第I块积木以其第k面朝上，第p块积木以第kc面朝上时，能否将积木I放在积木p的上面。1表示能，0表示不能。对于fi,j,k,有两种可能：1.除去第I块积木，第j根柱子的最上面的积木为编号为p的，若第p块积木以第kc面朝上，必须保证当第I块积木以k

20、面朝上时能够被放在上面，即cani,k,p,kc=1；2.第i块积木是第j根柱子的第一块积木，第j-1根柱子的最上面为第p块积木，则此时第p块积木可以以任意一面朝上。则有：动态规划)31,11(2,1,max)1,31,11(2,maxmax,kcipjiblockkcjpfkcpkicankcipjiblockkcjpfkjif且w 边界条件：w f1,1,1:=block1,1,3;f1,1,2:=block1,1,4;f1,1,3:=block1,1,5;w fi,0,k:=0;(1=i=n,1=k=3);w 时间复杂度为O(n2*m)免费馅饼 w SERKOI最新推出了一种叫做“免费馅

21、饼”的游戏。w 游戏在一个舞台上进行。舞台的宽度为W格，天幕的高度为H格，游戏者占一格。开始时，游戏者站在舞台的正中央正中央，手里拿着一个托盘。w 游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或右移动一格或两格，也可以站在愿地不动。w 馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时在8-308电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格/秒为单位。当馅饼在某一秒末恰好恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。w 写一个程序，帮助我们的游戏者收集馅饼，使得收集的馅饼的分数之和最大。免费馅饼w 输

22、入数据：输入文件的第一行是用空格分开的两个正整数，分别给出了舞台的宽度W（199之间的奇数）和高度H（1 100之间的整数）。w 接下来依馅饼的初始下落时间顺序给出了一块馅饼信息。由四个正整数组成，分别表示了馅饼的初始下落时刻（0 1000秒），水平位置、下落速度（1 100）以及分值。游戏开始时刻为0。从1开始自左向右依次对水平方向的每格编号。w 输出数据：输出文件的第一行给出了一个正整数，表示你的程序所收集到的最大分数之和。分析w 我们将问题中的馅饼信息用一个表格存储。表格的第I行第J列表示的是游戏者在第I秒到达第J列所能取得的分值。那么问题便变成了一个类似数字三角形的问题：从表格的第一行

23、开始往下走，每次只能向左或右移动一格或两格，或不移动走到下一行。怎样走才能得到最大的分值。w 因此，我们很容易想到用动态规划求解。w FI,J表示游戏进行到第表示游戏进行到第I秒，这时游戏者站在第秒，这时游戏者站在第J列时列时所能得到的最大分值。那么动态转移方程为：所能得到的最大分值。那么动态转移方程为：FI,J=Max FI-1,K +馅饼的分值馅饼的分值 (J-2=K=J+2)w 有一个三角形木板,竖直立放，上面钉着n(n+1)/2颗钉子，还有(n+1)个格子（当n=5时如图1）。每颗钉子和周围的钉子的距离都等于d，每个格子的宽度也都等于d，且除了最左端和最右端的格子外每个格子都正对着最下

24、面一排钉子的间隙。w 让一个直径略小于d的小球中心正对着最上面的钉子在板上自由滚落，小球每碰到一个钉子都可能落向左边或右边（概率各1/2），且球的中心还会正对着下一颗将要碰上的钉子。例如图2就是小球一条可能的路径。w 我们知道小球落在第i个格子中的概率概率pi=，其中i为格子的编号，从左至右依次为0,1,.,n。w 现在的问题是计算拔掉某些钉子后，小球落在编号为m的格子中的概率pm。假定最下面一排钉子不会被拔掉。例如图3是某些钉子被拔掉后小球一条可能的路径。钉子和小球 钉子和小球 w 输入：第1行为整数n（2=n=50）和m（0=m=n）。以下n行依次为木板上从上至下n行钉子的信息，每行中*表

25、示钉子还在，.表示钉子被拔去，注意在这n行中空格符可能出现在任何位置。w 输出：仅一行，是一个既约分数(0写成0/1)，为小球落在编号为m的格子中的概率pm分析w 设三角形有n行，第i行（1=i=n）有i个铁钉位置，其编号为0.i-1；第n+1行有n+1个铁钉位置，排成n+1个格子，编号为0.n。设经过位置（i,j）的小球个数为Pi,j，则落入格子m的小球个数为Pn+1,m，问题要求的是Pn+1,m/2n。w 假设位置(i,j)有铁钉，则各有Pi,j/2个小球落入位置（i+1,j）和位置(i+1,j+1)；否则Pi,j 个小球将全部落入位置(i+2,j+1)。w 可得如下算法：P1,0 2n;

26、for i1 to n dofor j1 to n do if 位置(i,j)有钉子 thenPi+1,j Pi+1,j+Pi,j/2;Pi+1,j+1 Pi+1,j+1+Pi,j/2;else Pi+2,j+1 Pi+2,j+1+Pi,j;w 问题求的是既约分数，因为分母为2的次幂，因此可把分子、分母同时约去2的因子，直至分子不能整除2。商店购物 某商店中每种商品都有一个价格。例如，一朵花的价格是2 ICU(ICU 是信息学竞赛的货币的单位）;一个花瓶的价格是5 ICU。为了吸引更多的顾客，商店提供了特殊优惠价。特殊优惠商品是把一种或几种商品分成一组。并降价销售。例如:3朵花的价格不是6而是

27、5 ICU;2个花瓶加1朵花是10 ICU不是12 ICU。编一个程序，计算某个顾客所购商品应付的费用。要充分利用优惠价以使顾客付款最小。请注意，你不能变更顾客所购商品的种类及数量，即使增加某些商品会使付款总数减小也不允许你作出任何变更。假定各种商品价格用优惠价如上所述，并且某顾客购买物品为:3朵花和2个花瓶。那么顾客应付款为14 ICU因为:1朵花加2个花瓶:优惠价:10 ICU 2朵花 正常价:4 ICU商店购物输入数据 第一个文件INPUTTXT的格式为:第一行是一个数字B（0B5），表示所购商品种类数。下面共B行，每行中含3个数C，K，P。C 代表商品的编码（每种商品有一个唯一的编码）

28、，1C999。K代表该种商品购买总数，1K5。P 是该种商品的正常单价（每件商品的价格），1P999。请注意，购物筐中最多可放5*525件商品。第二个文件OFFERTXT的格式为:第一行是一个数字S（0S99），表示共有S种优惠。下面共S行，每一行描述一种优惠商品的组合中商品的种类。下面接着是几个数字对（C，K），其中C代表商品编码，1C9 99。K代表该种商品在此组合中的数量，1K5。本行最后一个数字P（1 P9999）代表此商品组合的优惠价。当然，优惠价要低于该组合中商品正常价之总和。输出数据 在输出文件OUTPUTTXT中写 一个数字（占一行），该数字表示顾客所购商品（输入文件指明所购商

29、品）应付的最低货款。分析w 由于动态规划要满足无后效性和最优化原理，所以我们来分析此题是否满足以上两点。首先确定状态，商品不超过5种，而每种采购的数量又不超过5，那么用一个五元组来表示第i种商品买Ai的最小费用。w F F（A A1 1，A A2 2，A A3 3，A A4 4，A A5 5）（1 1）w 考虑这个状态的由来，当然，我们不用优惠商品也可以买，显然这样不是最优。于是如果我们能够使用第i条商品组合的话，状态就b变为了：w F F（A A1 1-S-SI1I1，A A2 2-S-SI2I2，A A3 3-S-SI3I3，A A4 4-S-SI4I4，A A5 5-S-SI5I5）（2

30、 2）w 这样的话，状态1的费用为状态2的费用加上Si的费用，而状态2的费用必须最低（很显然，用反证法即可），同时，我们也不管状态2是如何来的（因为每一个优惠商品组合的使用是没有限制的），所以本题既满足无后效性，又符合最优化原理，同时还有大量重叠子问题产生，动态规划解决此题是最好不过了。状态转移方程w F a,b,c,d,e=MinFa-Si1,b-Si2,c-Si3,d-Si4,e-Si5+SaleCostSi (0=i=S,0=a,b,c,d,e=5)初始条件为：F a,b,c,d,e=Cost1*a+Cost2*b+Cost3*c+Cost4*d+Cost5*e添括号问题 w 有一个由数

31、字1，2，.，9组成的数字串（长度不超过200），问如何将M(M=20)个加号(+)插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。w 注意：w 加号不能加在数字串的最前面或最末尾，也不应有两个或两个以上的加号相邻。w M保证小于数字串的长度。w 例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式的值133。w 输入格式w 从键盘读入输入文件名。数字串在输入文件的第一行行首（数字串中间无空格且不折行），的值在输入文件的第二行行首。w 输出格式w 在屏幕上输出所求得的最小和的精确值。分析w 考虑到数据的规模超过了长整型,我们注意在解题过

32、程中采用高精度算法.w 规划方程:w FI,J=MIN FI-1,K+NUMK+1,J (I-1=K=J-1)w 边界值:F0,I:=NUM1,I;w FI，J表示前J个数字中添上I个加号后得到的最小值。w NUMI，J表示数字串第I位到第J位的数w 上述问题的每一步，都只与上一步有关。因此可以采用滚动数组w 程序的时间效率约为 20*200*200 最长前缀 w 一些生物体的复杂结构可以用其基元的序列表示，而一个基元用一个大写英文字符串表示。生物学家的一个问题就是一个这样的长序列分解为基元（字符串）的序列。对于给定的基元集合P，如果可以从中选出N个基元P1，P2，P3，.,Pn，将它们各自对

33、应的字符串依次连接后得到一个字符串S，称S可以由基元集合P构成。在从P中挑选基元时，一个基元可以使用多次，也可不用。例如，序列 ABABACABAAB 可以由基元集合A，AB，BA，CA，BBC 构成。w 字符串的前K个字符为该字符串的前缀，其长度为K。请写一个程序，对于输入的基元集合P和字符串T，求出一个可以由基元集合P构成的字符串T的前缀，要求该前缀的长度尽可能长，输出其长度。最长前缀w 输入数据：有两个输入文件 INPUT.TXT，DATA.TXTINPUT.TXT 的第一行是基元集合P中的基元数目N（1=N=100）,随后有2N行，每两行描述一个基元，第一行为该基元的长度L（1=L=2

34、0）。随后一行是一个长度为L的大写英文字符串，表示该基元。每个基元互不相同。DATA.TXT 描述要处理的字符串T，每一行行首有一个大写字母，最后一行是一个字符.,表示字符串结束。T的长度最小为1，最大不超过500000。w 输出数据：OUTPUT.TXT。只有一行，一个数字，表示可以由P构成的T的最长前缀的长度。分析w 本题可以简述为:从一个集合里选出若干个基元,使其组成字符串T的前缀,求最长前缀的长度.w 对于T的每个字符，其状态可分为两种：w 在此之前的所有字符（包括本身）可匹配(true)、不可匹配(false)。(可匹配是指可以由集合里的基元组成)w 用Fi表示第i个字符的状态，fi

35、nda,b表示由第a至b位的字符组成的子串是否存在于集合中，则，Fi=Fi or(Fk and findk+1,j)(0=k=i-1)w 初始条件:if i=0 then Fi:=true else Fi:=false分析w 由于T的长度最大达500000，无法存放所有状态，但集合里基元长度不超过20，因此可只保留当前20位字符与状态。当20位字符都不可以匹配时，停止运算，最后一个状态为true的字符的位置，即为所求。w 为了便于操作，可用字符串表示状态，0表false、1表true.w 为了便于查找，可将基元按长度存储。w 形如：si,j，表示长度为 i的第 j个基元。w 亦可采用树的结构存

36、储基元，构造一种多叉树（最多26叉），查找时顺着相应字母，定位到相应分支。这样速度要快些，但程序更复杂。大家可以比较一下。w 按树结构算，时间复杂度为O(500000*L*L),勉强可以承受。多边形 w 多角形是一个单人玩的游戏，开始时有一个N个顶点的多边形。如图，这里N N=4。每个顶点有一个整数标记，每条边上有一个“+”号或“*”号。边从1编号到N。第一步，一条边被拿走；随后各步包括如下：w 选择一条边E和连接着E的两个顶点V V1和 V V2；w 得到一个新的顶点，标记为V1与V2通过边E E上的运算符运算的结果。w 最后，游戏中没有边，游戏的得分为仅剩余的一个顶点的值。-7425+*1

37、234+*样例-7 4 2 5+*1 2 4+42+*24-24+2-40写一个程序，对于给定一个多边形，计算出可能的最高得分，并且列出得到这个分数的过程。分析 分析w 我们在这条“线”当中继续删边，并且每次删边都使被删边两旁的点按边上的操作符合并，图五。这样进行了n-1次删边操作后，“线”变成了一个点。我们的目的，就是安排删边的顺序，使最后的点上的数尽可能的大。w 拿到题目之后，我们马上可以想到用枚举法枚举删边的先后顺序。但边数最大可以达到50，枚举的复杂将会有50！。因此枚举算法马上被排除了。w 对最优化问题的求解，我们往往可以使用动态规划来解决。这道题是不是可以使用动态规划呢？w 我们先

38、对题目进行一些变化原题中顶点上的数可以为负数，现在我们规定这个数一定大于等于0；原题中边可以为乘号，现在我们规定只能为加号。w 题意改变后，我们想到了什么？对！“石子合并”。动态规划w 我们先枚举第一次删掉的边，然后再对每种状态进行动态规划求最大值 w 用f(I,j)表示从j开始，进行i次删边操作所能得到的最大值，num(i)表示第i个顶点上的数，那么：)(),1(),(),(max),(11inumifkikjfikfjifik进一步分析w 现在我们来考虑加入乘号后的情况。w 由于所有的顶点上的数都为非负数，因此即使有了乘法，函数f的无后效性并不被破坏。我们可以在前一方程的基础上进行改进：（

39、opr(i)表示第i条边上的操作符）)(),1(),(max),(11inumifkikjikactjifiky2)f(x2,*y1)f(x1,-1)-opr(x2y2)f(x2,y1)f(x1,1)-opr(x2)2,2,1,1(时，当时，当yxyxAct进一步分析w 最后，我们允许顶点上出现负数。以前的方程还适不适用呢？w 这个例子的最优解应该是（3+2）*（-9）*（-5）=250，然而如果沿用以前的方程，得出的解将是（-10）*3+2）*（-5）=140。为什么？w 我们发现，两个负数的积为正数；这两个负数越小，它们的积越大。我们从前的方程，只是尽量使得局部解最大，而从来没有想过负数的

40、积为正数这个问题。-932-5*图六+最终？w 我们引入函数fmin和fmax来解决这个问题。fmax(I,j)表示从j开始，进行i次删边操作所能得到的最大值，fmin(I,j)表示从j开始，进行i次删边操作所能得到的最小值。)(),1(),min(min),min(),max(max),max(1111inumifkikjikactjifkikjikactjifikik函数actmax与actmin的构造是十分关键的。首先讨论actmax(x1,y1,x2,y2)的构造：当opr(x2-1)=+时，actmax=fmax(x1,y1)+fmax(x2,y2)当opr(x2-1)=*时，act

41、max=max(fmax(x1,y1)*fmax(x2,y2),fmin(x1,y1)*fmin(x2,y2)完美解决w 接下来讨论actmin(x1,y1,x2,y2)的构造：w 当opr(x2-1)=+时，actmin=fmin(x1,y1)+fmin(x2,y2)w opr(x2-1)=*时，actmin=min(fmax(x1,y1)*fmin(x2,y2),fmin(x1,y1)*fmax(x2,y2)w 到此为止，整个问题圆满解决了。算法的空间复杂度为n2，算法时间复杂度为n4（先要枚举每一条边，然后再用复杂度为n3的动态规划解决）。选课 w 大学里实行学分。每门课程都有一定的学分

42、，学生只要选修了这门课并考核通过就能获得相应的学分。学生最后的学分是他选修的各门课的学分的总和。w 每个学生都要选择规定数量的课程。其中有些课程可以直接选修，有些课程需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如，数据结构必须在选修了高级语言程序设计之后才能选修。我们称高级语言程序设计是数据结构的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。为便于表述每门课都有一个课号，课号依次为1，2，3，。选课w 下面举例说明w 上例中1是2的先修课，即如果要选修2，则1必定已被选过。同样，如果要选修3，那么1和2都一定已被选修过。w 学生不可能学完大学所开设的

43、所有课程，因此必须在入学时选定自己要学的课程。每个学生可选课程的总数是给定的。现在请你找出一种选课方案，使得你能得到学分最多，并且必须满足先修课优先的原则。假定课程之间不存在时间上的冲突。选课w 输入输入 输入文件的第一行包括两个正整数M、N（中间用一个空格隔开）其中M表示待选课程总数（1M1000)，N表示学生可以选的课程总数（1NM)。以下M行每行代表一门课，课号依次为1，2M。每行有两个数（用一个空格隔开），第一个数为这门课的先修课的课号（若不存在先修课则该项为0），第二个数为这门课的学分。学分是不超过10的正整数。w 输出输出 输出文件第一行只有一个数，即实际所选课程的学分总数。以下N

44、行每行有一个数，表示学生所选课程的课号。样例分析7 42 20 10 42 17 17 62 2表12157346图202157346图1分析w 们可以选取某一个点k的条件只是它的父节点已经被选取或者它自己为根节点；而且我们不论如何取k的子孙节点，都不会影响到它父节点的选取情况，这满足无后效性原则。于是我们猜测，是不是可以以节点为阶段，进行动态规划呢？w 我们用函数f(I,j)表示以第i个节点为父节点，取j个子节点的最佳代价，则：w 可是如此规划，其效率与搜索毫无差别，虽然我们可以再次用动态规划来使它的复杂度变为平方级，但显得过于麻烦。jnchnchjnchnchnchjnchnichnchn

45、chjchinchinchifnchchfnchchfjif111122113)1(21),()2,2()1,1(max),(改造树w 转变为二叉树。如果两节点a,b同为兄弟，则将b设为a的右节点；如果节点b是节点a的儿子，则将节点b设为节点a的左节点。树改造完成后如图3。w 我们用函数f(I,j)表示以第i个节点为父节点，取j个子节点的最佳代价，这和前一个函数表示的意义是一致的，但方程有了很大的改变：023014765图3动态规划w 这个方程的时间复杂度最大为n3，十分优秀了。w 在具体实现这道题时，我们可以自顶而下，用递归进行树的遍历求解 jlcnlcnjrightcflcnleftcfj

46、if1),(),(max),(陨石的秘密 w 公元11380年，一颗巨大的陨石坠落在南极。于是，灾难降临了，地球上出现了一系列反常的现象。当人们焦急万分的时候，一支中国科学家组成的南极考察队赶到了出事地点。经过一番侦察，科学家们发现陨石上刻有若干行密文，每一行都包含5个整数：w 1 1 1 1 61 1 1 1 6w 0 0 6 3 570 0 6 3 57w 8 0 11 3 28458 0 11 3 2845w 著名的科学家SS发现，这些密文实际上是一种复杂运算的结果。为了便于大家理解这种运算，他定义了一种SS表达式：陨石的秘密w 1 SS表达式是仅由，（，）组成的字符串。w 2 一个空串

47、是SS表达式。w 3 如果A是SS表达式，且A中不含字符，则(A)是SS表达式。w 4 如果A是SS表达式，且A中不含字符，则A是SS表达式。w 5 如果A是SS表达式，则A是SS表达式。w 6 如果A和B都是SS表达式，则AB也是SS表达式。w 例如w()()()()，()()()()，()()，都是SS表达式。w 而()()()()()()，()()，不是SS表达式。陨石的秘密w 一个SS表达式E的深度D(E)定义如下 0,()()1,(),max(),(),A,BED ED AEAEAEAASSD A D BEABSS如果 是空串如果或者或者其中 是表达式如果其中是表达式。w 例如()(

48、)的深度为2。w 密文中的复杂运算是这样进行的：w 设密文中每行前4个数依次为L1，L2，L3，D，求出所有深度为D，含有L1对，L2对，L3对()的SS串的个数，并用这个数对当前的年份11380求余数，这个余数就是密文中每行的第5个数，我们称之为“神秘数”。w 密文中某些行的第五个数已经模糊不清，而这些数字正是揭开陨石秘密的钥匙。现在科学家们聘请你来计算这个神秘数。陨石的秘密w 输入文件（secret.in）w 共一行，4个整数L1，L2，L3，D。相邻两个数之间用一个空格分隔。w（0L110，0L210，0L310，0D30）w 输出文件（secret.out）w 共一行，包含一个整数，即

49、神秘数。w 输入样例w 1 1 1 2w 输出样例w 8条件的简化条件的简化 w 题目对于什么是SS表达式做了大量的定义，一系列的条件让我们如坠雾中。为了看清SS表达式的本质，有必要对条件进行简化。w 条件1描述了SS表达式的元素。w 条件3、4、5实际上对于()、的嵌套顺序做了限制，即()内不能嵌套、，内不能潜逃。概括起来是两点：SS表达式中括号要配对；、（）从外到内依次嵌套。状态的表示状态的表示w 这是动态规划过程中首先要解决的一个问题。本题的条件看似错综复杂，状态不易提炼出来，实际上，题目本身已经为我们提供了一个很好的状态表示法。w 对于一个表达式来说，它含有的元素是“（”，“）”，“”

50、，“”，“”，“”，此外，定义了深度这一概念。最简单的一种想法是：按照题目的所求，直接把的对数l1、的对数l2、()的对数l3以及深度d作为状态表示的组成部分，即用(l1,l2,l3,d)这样一个四元组来确定一个状态。令F(l1,l2,l3,d)表示这样一个状态所对应的神秘数，于是F(L1,L2,L3,D)对应问题答案。此外，我们令G(l1,l2,l3,d)表示含有l1个，l2个，l3个()，深度不大于d的表达式个数。显然，F(l1,l2,l3,d)=G(l1,l2,l3,d)-G(l1,l2,l3,d-1)。于是求解F的问题，可以转化为求解G的问题。状态转移方程状态转移方程 w 设当前的状态

51、为（l1,l2,l3,d），根据表达式的第一位的值，分如下三种情况：w 情况一：第一位是“（”，与其配对的“）”位于第i位。设表示这种情况下的总数，G1(l1,l2,l3,d)、类似定义。（）ss1 i ss21301),13,2,1(*)1,0,0(),3,2,1(lzdzlllGdzGdlllG情况一计算的复杂度为O(n5)状态转移方程状态转移方程w 情况二：第一位是“”，与其配对的“”位于第i位 ss1 i ss23,122),3,12,1(*)1,0(),3,2,1(lzlydzlyllGdzyGdlllG计算复杂度为O(n6)。状态转移方程状态转移方程w 情况三：第一位是“”，与其配对的“”位于第i位。ss1 i ss23,2113),3,2,11(*)1,(),3,2,1(lzlylxdzlylxlGdzyxGdlllG计算复杂度为O(n7)。小结),3,2,1(),3,2,1(),3,2,1(),3,2,1(321dlllGdlllGdlllGdlllG本题的时间复杂度为O(n7)，在规定时间内完全可以出解。空间上，若采用滚动数组的方式，可将空间复杂度为n3，保存也不成问题。本题的难点在于动态规划时情况的划分及处理，当需要建立复杂的状态转移方程时，我们也要保持冷静、抓住要害。