合并类动态规划

1、合并类动态规划,YALI 朱全民,凸多边形三角划分,给定一个具有N（N50）个顶点（从1到N编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？ 输入文件：第一行 顶点数N 第二行 N个顶点（从1到N）的权值 输出格式：最小的和的值 各三角形组成的方式 输入示例：5 122 123 245 231 输出示例：The minimum is ：12214884 The formation of 3 triangle: 3 4 5, 1 5 3, 1 2 3,分析,设FI,J（IJ）表示从顶点I到顶点J的凸多边形三角剖分后所

2、得到的最大乘积，我们可以得到下面的动态转移方程： FI,J=MinFI,K+FK,J+SI*SJ*SK (0IKJ=N) 初始条件:F1，2=0 目标状态:F1,N 但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过长整形范围，所以还需用高精度计算,石子合并,在一园形操场四周摆放N堆石子(N100),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(20), (1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少 (2) 选择一种合并石子的方案,使得做N-1次合并,得分的总和

3、最大 输入数据: 第一行为石子堆数N; 第二行为每堆石子数,每两个数之间用一空格分隔. 输出数据 : 从第1至第N行为得分最小的合并方案. 第N+1行为空行.从N+2到2N+1行是得分最大的合并方案.,示例,贪心法,动态规划,用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颗石

4、子合并所得的最小值，可以得到类似的方程： mini,j = min(mini, k + mini + k, j k + datai,k + datai+k, j k) (0=k=j) mini,0 = 0 这样，我们完美地解决了这道题。时间复杂度也是O(n2)。,多边形,多角形是一个单人玩的游戏，开始时有一个N个顶点的多边形。如图，这里N=4。每个顶点有一个整数标记，每条边上有一个“+”号或“*”号。边从1编号到N。 第一步，一条边被拿走；随后各步包括如下： 选择一条边E和连接着E的两个顶点V1和 V2； 得到一个新的顶点，标记为V1与V2通过边E上的运算符运算的结果。 最后，游戏中没有边，游

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

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

7、该是（3+2）*（-9）*（-5）=250，然而如果沿用以前的方程，得出的解将是（-10）*3+2）*（-5）=140。为什么？ 我们发现，两个负数的积为正数；这两个负数越小，它们的积越大。我们从前的方程，只是尽量使得局部解最大，而从来没有想过负数的积为正数这个问题。,最终？,我们引入函数fmin和fmax来解决这个问题。fmax(I,j) 表示从j开始，进行i次删边操作所能得到的最大值，fmin(I,j) 表示从j开始，进行i次删边操作所能得到的最小值 。,函数actmax与actmin的构造是十分关键的。 首先讨论actmax(x1,y1,x2,y2)的构造： 当opr(x2-1)=+时，

8、actmax=fmax(x1,y1)+fmax(x2,y2) 当opr(x2-1)=*时， actmax=max(fmax(x1,y1)*fmax(x2,y2),fmin(x1,y1)*fmin(x2,y2),完美解决,接下来讨论actmin(x1,y1,x2,y2)的构造： 当opr(x2-1)=+时，actmin=fmin(x1,y1)+fmin(x2,y2) opr(x2-1)=*时， actmin=min(fmax(x1,y1)*fmin(x2,y2),fmin(x1,y1)*fmax(x2,y2) 到此为止，整个问题圆满解决了。算法的空间复杂度为n2，算法时间复杂度为n4（先要枚举每

9、一条边，然后再用复杂度为n3的动态规划解决）。,能量项链,在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。,需要时，Mars人就用吸盘夹住相邻的两颗

10、珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。 例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3) (3，5) (5，10) (10，2)。我们用记号表示两颗珠子的聚合操作，(jk)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：(41)=10*2*3=60。 这一串项链可以得到最优值的一个聚合顺序所释放的总能量为 (41)2)3）=10*2*3+10*3*5+10*5*10=710。,【输入文件】 输入文件energy.in的第一行是一个正整数N（4N10

11、0），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1iN），当i时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。 至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。 【输出文件】 输出文件energy.out只有一行，是一个正整数E（E2.1*109），为一个最优聚合顺序所释放的总能量。,分析,先枚举一个位置p，将珠子变成一条链。设链中的第i颗珠子头尾标记为(Si-1与Si)。令Gi,j表示从第i颗珠子一直合

12、并到第j颗珠子所能产生的最大能量，则： Gi,j=minGi,k+Gk+1,j+Si-1*Sk*Sj, i=kj 边界条件： Gi,i=0 最后的最优解为G1,n 该算法需要枚举p,i,j,k，而且每一重枚举都是O(n)，所以总的时间复杂度为O(n4)，而n可能有100，因此直接实现这个算法有超时的危险。,在上式中，我们的方程只和珠子的标记(即Si)有关，而与编号无关，因此，珠子从1到n编号和2到n+1编号是等效的。现在不枚举p，令Si=Si mod n (n=i=2n)，仍用上面的方程计算，则计算所得的G1,n为从第一颗珠子前断开时最优值，而G2,n+1计算的正好是从第二颗珠子前断开时的最优

13、值。Gi,n+i-1表示从第i颗前断的最优值。利用这种方法将长为n的环变为了长为2n的链，却能不能枚举p而算得最优值。 一般而言，如果是对环的最优值问题能通过枚举断点而求得最优解，都可以将环拉成链后复制一遍，求出链中所有长为n的段的最优值，此值即为环中对应的最优解。这此对环的动态规划最简单也是最常用的降维方法。 通过拉伸后，复杂度降为了O(n3)，可以迅速出解。,Blocks,Jimmy最近迷上了一款叫做方块消除的游戏. 游戏规则如下：n个带颜色方格排成一列，相同颜色的方块连成一个区域（如果两个相邻的方块颜色相同，则这两个方块属于同一个区域). 游戏时，你可以任选一个区域消去.设这个区域包含的

14、方块数为x,则将得到x2的分值.方块消去之后，右边的方格将向左移动. 虽然游戏很简单，但是要得到高分也不是很容易.Jimmy希望你帮助他找出最高可以得到多少分 N200.,Sample,如图，依次消去灰,白,黑区域，你将得到42+32+22=29分，这是最高得分.,算法分析,合并颜色序列，如 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段. 上面

15、的颜色序列中, m = 5, color1 . 5=(1,3,2,4,5) len 1 . 5=(3,2,1,3,2),定义状态 设S(i,j,k)为(colori,leni),(colori+1,leni+1) (colorj-1,lenj-1)的连续同色整段以及在一系列消除操作后j后接了k个颜色为colorj的方块(colorj,lenj+k)的一个颜色序列. 设f(i,j,k)表示消除S(i,j,k)这一个颜色序列可以得到的最大分值.,算法分析,算法分析,动态规划转移 如果立刻将(colorj,lenj+k)这一段消除，则转移为f(i,j-1,0)+(lenj+k)2 如果lenj+k暂时不消除而连接到上一个颜色相同的块上,则转移为f(i,p,k+lenj)+f(p+1,j-1,0). 其中colorp=colorj, i=pj,动态规划转移方程 f(i,j,k)=Maxf(i,j-1,0