线性类动态规划

1、最长上升序列 设有整数序列b1,b2,b3,bm，若存在下标i1i2i3 in，且bi1bi2bi3 bin，则称 b1,b2,b3,bm中有长度为n的上升序列bi1 , bi2 ,bi3 ,bin 。求序列b1,b2,b3,bm中所有长度(n)最大上升子序列输入：整数序列。输出：最大长度n和所有长度为n的序列个数。1分析设f(i)为前i个数中的最长上升序列长度 , 则f(i)=maxf(j)+1 (1=ji=m, bjbi)边界为F(1)=12分析设t(i)为前i个数中最长不下降序列的个数,则t(i)=t(j) (1=ji=m , bjbi, f(i)=f(j)+1) 初始为t(i)=1当f

2、(i)=n时，将t(i)累加举例： 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=43进一步(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 2 3 5 ，4个1 2 3 44改进算

3、法上例显然对于相两个相同的数，重复算了多次因此，我们对算法进行改进：对原序列按b从小到大（当bi=bj时按F从大到小）排序，增设Order(i)记录新序列中的i个数在原序列中的位置。可见，求t(i)时，当f(j)=f(j+1),b(j)=b(j+1)且Order(j+1)Order(i)时，便不累加t(j)。这样就避免了重复。 上述算法的时间复杂度为O(n2) 5添括号问题 有一个由数字1，2，. ，9组成的数字串（长度不超过200），问如何将M(M=20)个加号(+)插入到这个数字串中，使所形成的算术表达式的值最小。请编一个程序解决这个问题。注意：加号不能加在数字串的最前面或最末尾，也不应有

4、两个或两个以上的加号相邻。M保证小于数字串的长度。例如：数字串79846，若需要加入两个加号，则最佳方案为79+8+46，算术表达式的值133。6分析考虑到数据的规模超过了长整型,我们注意在解题过程中采用高精度算法.规划方程:FI,J = MIN FI-1,K + NUMK+1,J (I-1=K=J-1)边界值:F0,I := NUM1,I;FI，J表示前J个数字中添上I个加号后得到的最小值。NUMI，J表示数字串第I位到第J位的数上述问题的每一步，都只与上一步有关。因此可以采用滚动数组程序的时间效率约为 20 * 200 * 200 7演唱会一场演唱会即将举行。现有N（ON=200）个歌迷排

5、队买票，一个人买一张，而售票处规定，一个人每次最多只能买两张票。假设第I位歌迷买一张票需要时间Ti（1=I=n），队伍中相邻的两位歌迷（第j个人和第j+1个人）也可以由其中一个人买两张票，而另一位就可以不用排队了，则这两位歌迷买两张票的时间变为Rj，(假如RjTj+Tj+1，则这样做就可以缩短后面歌迷等待的时间，加快整个售票的进程 )。现给出N，Ti和Ri，求使每个人都买到票的最短时间和方法。8分析设f（i）为前i个人花费最短时间于是有f（i）=minf（i-1）+Ti，f（i-2）+Ri-1，初始f（0）=0，f（1）=T19复制书稿假设有M本书（编号为1，2，M），想将每本复制一份，M本书

6、的页数可能不同（分别是P1，P2，PM）。任务：将这M本书分给K个抄写员(K=M) 每本书只能分配给一个抄写员进行抄写，而每个抄写员所分配到的书必须是连续顺序的。10分析设F（I，J）为前I个抄写员复制前J本书的最小“页数最大数”。于是有 F（I，J）=MINmax F（I-1，V），T（V+1，J） （1=I=K，I=J=M-K+I，I-1=V=J-1。 其中T（V+1，J）表示从第V+1本书到第J本书的页数和。起步时F（1，1）=P1。11多米诺骨牌 有一种多米诺骨牌是平面的，其正面被分成上下两部分，每一部分的表面或者为空，或者被标上1至6个点。现有一行排列在桌面上：例如，顶行骨牌的点数之

7、和为6+1+1+1=9；底行骨牌点数之和为1+5+3+2=11。顶行和底行的差值是2。这个差值是两行点数之和的差的绝对值。每个多米诺骨牌都可以上下倒置转换，即上部变为下部，下部变为上部。现在的任务是，以最少的翻转次数，使得顶行和底行之间的差值最小。12分析以骨牌序列上下两部分的差值I作为状态，把达到这一状态的翻转步数作为状态值，记为f（I）。于是有 f（I）=minf（I+J）+1 （-12=J=12,J为偶数，且要求当前状态有差值为J/2的骨牌）。这里，I不是无限增大或减小，其范围取决于初始骨牌序列的数字差的和的大小。 13系统可靠性 一个系统由若干部件串联而成，只要有一个部件故障，系统就不

8、能正常运行，为提高系统的可靠性，每一部件都装有备用件，一旦原部件故障，备用件就自动进入系统。显然备用件越多，系统可靠性越高，但费用也越大，那么在一定总费用限制下，系统的最高可靠性等于多少？给定一些系统备用件的单价Ck，以及当用Mk个此备用件时部件的正常工作概率Pk（Mk），总费用上限C。求系统可能的最高可靠性。 输入文件格式：第一行：n C第二行：C1 P1(0) P1(1) P1(X1) （0=X1=C/Ck） 第 n 行：Cn Pn(0) Pn(1) Pn(Xn) （0=Xn=C/Cn）14分析例：输入：2 20 3 0 .6 0.65 0.7 0.75 0.8 0.85 0.9 5 0.

9、7 0.75 0.8 0.8 0.9 0.95 输出：0.6375设FI,money表示将money的资金用到前I项备用件中去的最大可靠性，则有 FI,money = maxFI-1 ,moneyk*CostI (0=I=n,0=K= money div Cost(I) )初始： F0,0=0目标： Fn,C=015航空旅行给定一张航空图，图中的顶点代表城市，边代表两城市的直通航线。现要求找出一条满足下述限制条件的、含城市最多的旅游路线：1.从最西的一个城市出发，单方向从西向东途经若干城市到达最东的一个城市，然后再单方向从东向西飞回起点（可途经若干城市）；2.除起点城市外，任何城市只能访问一次

10、，起点城市被访问两次：出发一次，返回一次。16分析设fi,j表示顶点i至顶点N与顶点j至顶点N的两条路线的最多顶点数，很容易得出，fN,N=1,fi,N=2（当该阶段中顶点i与顶点N间有直通航线），ai,j=aj,i。这样，可以得到以下关系式：fi,j=maxfk,j+1,fi,j (kj且边(k,i)存在且ak,j0) 时间复杂度为O(N3)17积木游戏 有N块长方体积木，编号依次为1,2,N 。第i块长宽高分别为ai,bi,ci（i=1,2,N），要从中选出若干块，将他们摞成M（1= M = N=n），x,y是上面一块积木接触面的两条边（x=y），则一定满足m.=x和n=y；下面的积木的编

11、号要小于上面的积木的编号。请你编一程序，寻找一种游戏方案，使得所有能摞成的M根柱子的高度之和最大。18分析设（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块积木

12、，第j根柱子的最上面的积木为编号为p的，若第p块积木以第kc面朝上，必须保证当第I块积木以k面朝上时能够被放在上面，即cani,k,p,kc=1； 2. 第i块积木是第j根柱子的第一块积木，第j-1根柱子的最上面为第p块积木，则此时第p块积木可以以任意一面朝上。19动态规划边界条件：f1,1,1:=block1,1,3; f1,1,2:=block1,1,4; f1,1,3:=block1,1,5;fi,0,k:=0; (1= i = n, 1= k = 3);时间复杂度为O(n2*m) 20石子合并 在一园形操场四周摆放N堆石子(N100),现要将石子有次序地合并成一堆.规定每次只能选相临的

13、两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(20),(1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少 (2) 选择一种合并石子的方案,使得做N-1次合并,得分的总和最大21示例22贪心法 N=5 石子数分别为3 4 6 5 4 2。用贪心法的合并过程如下：第一次 3 4 6 5 4 2得分 5第二次 5 4 6 5 4得分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第三次

14、13 5 4 2得分6第四次13 5 6得分11第五次 13 11得分24第六次24总分：61显然，贪心法是错误的。 23动态规划 用datai,j表示将从第i颗石子开始的接下来j颗石子合并所得的分值，maxi,j表示将从第i颗石子开始的接下来j颗石子合并可能的最大值，那么：maxi,j = max(maxi, k + maxi + k, j k + datai,k + datai+k, jk) (2=k=j)maxi,1 = 0同样的，我们用mini,j表示将第从第i颗石子开始的接下来j颗石子合并所得的最小值，可以得到类似的方程：mini,j = min(mini, k + mini + k

15、, j k + datai,k + datai+k, j k) (0=k=j)mini,0 = 0这样，我们完美地解决了这道题。时间复杂度也是O(n2)。24多边形 多角形是一个单人玩的游戏，开始时有一个N个顶点的多边形。如图，这里N=4。每个顶点有一个整数标记，每条边上有一个“+”号或“*”号。边从1编号到N。 第一步，一条边被拿走；随后各步包括如下：选择一条边E和连接着E的两个顶点V1和 V2；得到一个新的顶点，标记为V1与V2通过边E上的运算符运算的结果。最后，游戏中没有边，游戏的得分为仅剩余的一个顶点的值。 25样例写一个程序，对于给定一个多边形，计算出可能的最高得分，并且列出得到这个

16、分数的过程。26分析 27分析我们先枚举第一次删掉的边，然后再对每种状态进行动态规划求最大值 用f(i,j)表示从j开始，进行i次删边操作所能得到的最大值，num(i)表示第i个顶点上的数，若为加法，那么：28进一步分析最后，我们允许顶点上出现负数。以前的方程还适不适用呢？这个例子的最优解应该是（3+2）*（-9）*（-5）=250，然而如果沿用以前的方程，得出的解将是（-10）*3+2）*（-5）=140。为什么？我们发现，两个负数的积为正数；这两个负数越小，它们的积越大。我们从前的方程，只是尽量使得局部解最大，而从来没有想过负数的积为正数这个问题。 -932-5*图六+29最终？我们引入函

17、数fmin和fmax来解决这个问题。fmax(i,j) 表示从j开始，进行i次删边操作所能得到的最大值，fmin(i,j) 表示从j开始，进行i次删边操作所能得到的最小值 。当OP=+Fmax(i,j)=maxfmax(i,k)+fmax(k+1,j)Fmin(i,j)=minfmin(i,k)+fmin(k+1,j)30完美解决初始值 Fmax(i,i)=num(i) Fmin(i,i)=num(i)到此为止，整个问题圆满解决了。算法的空间复杂度为O(n2)，算法时间复杂度为O(n4)(先要枚举每一条边，然后再用复杂度为O(n3 )的动态规划解决）。31Blocks Jimmy最近迷上了一款

18、叫做方块消除的游戏. 游戏规则如下：n个带颜色方格排成一列，相同颜色的方块连成一个区域（如果两个相邻的方块颜色相同，则这两个方块属于同一个区域). 游戏时，你可以任选一个区域消去.设这个区域包含的方块数为x,则将得到x2的分值.方块消去之后，右边的方格将向左移动.虽然游戏很简单，但是要得到高分也不是很容易.Jimmy希望你帮助他找出最高可以得到多少分N200.32Sample如图，依次消去灰,白,黑区域，你将得到42+32+22=29分，这是最高得分.33算法分析合并颜色序列，如 1 1 1 3 3 2 4 4 4 5 5 根据方块消除的规则，连在一起的相同颜色方块可以合并 上面的颜色序列为(1,3),(3,2),(2,1),(4,3),(5,2),其中(a,b)表示有b个颜色为a的连在一起.于是题目可以表示成colori,leni,1=i=m, m表示颜色序列总共有m段. 上面的颜色序列中, m = 5, color1 . 5=(1,3,2,4,5)len 1 . 5=(3,2,1,3,2)34定义状态设S(i,j,k)为(colori,leni),(colori+1,leni+1) (colorj-1,lenj-1)的连续同色整段以及在一系列消除操作后j后接了k个颜色为colorj的方块(colorj,lenj+k)的一个颜色序列.设f(i,j,k)表示