合并类动态规划

合并类动态规划YALI朱全民凸多边形三角划分给定一个具有N（N50）个顶点（从1到N编号）的凸多边形，每个顶点的权均已知。问如何把这个凸多边形划分成N-2个互不相交的三角形，使得这些三角形顶点的权的乘积之和最小？输入文件：第一行顶点数N第二行N个顶点（从1到N）的权值输出格式：最小的和的值各三角形组成的方式输入示例：5122123245231输出示例：Theminimumis：12214884Theformationof3triangle:345,153,123分析设F[I,J]（IJ）表示从顶点I到顶点J的凸多边形三角剖分后所得到的最大乘积，我们可以得到下面的动态转移方程：F[I,J]=Min{F[I,K]+F[K,J]+S[I]*S[J]*S[K]}(0IKJ=N)初始条件:F[1，2]=0目标状态:F[1,N]但我们可以发现,由于这里为乘积之和，在输入数据较大时有可能超过长整形范围，所以还需用高精度计算石子合并在一园形操场四周摆放N堆石子(N≤100),现要将石子有次序地合并成一堆.规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。编一程序,由文件读入堆数N及每堆石子数(≤20),(1)选择一种合并石子的方案,使得做N-1次合并,得分的总和最少(2)选择一种合并石子的方案,使得做N-1次合并,得分的总和最大输入数据:第一行为石子堆数N;第二行为每堆石子数,每两个数之间用一空格分隔.输出数据:从第1至第N行为得分最小的合并方案.第N+1行为空行.从N+2到2N+1行是得分最大的合并方案.示例贪心法N=5石子数分别为346542。用贪心法的合并过程如下：第一次346542得分5第二次54654得分9第三次9654得分9第四次969得分15第五次159得分24第六次24总分：62然而仔细琢磨后，发现更好的方案：第一次346542得分7第二次76542得分13第三次13542得分6第四次1356得分11第五次1311得分24第六次24总分：61显然，贪心法是错误的。动态规划用data[i,j]表示将从第i颗石子开始的接下来j颗石子合并所得的分值，max[i,j]表示将从第i颗石子开始的接下来j颗石子合并可能的最大值，那么：max[i,j]=max(max[i,k]+max[i+k,j–k]+data[i,k]+data[i+k,j–k])(2=k=j)max[i,1]=0同样的，我们用min[i,j]表示将第从第i颗石子开始的接下来j颗石子合并所得的最小值，可以得到类似的方程：min[i,j]=min(min[i,k]+min[i+k,j–k]+data[i,k]+data[i+k,j–k])(0=k=j)min[i,0]=0这样，我们完美地解决了这道题。时间复杂度也是O(n2)。多边形多角形是一个单人玩的游戏，开始时有一个N个顶点的多边形。如图，这里N=4。每个顶点有一个整数标记，每条边上有一个“+”号或“*”号。边从1编号到N。第一步，一条边被拿走；随后各步包括如下：选择一条边E和连接着E的两个顶点V1和V2；得到一个新的顶点，标记为V1与V2通过边E上的运算符运算的结果。最后，游戏中没有边，游戏的得分为仅剩余的一个顶点的值。-7425+*1234+*样例-7425+*124+42+*24-24+2-40写一个程序，对于给定一个多边形，计算出可能的最高得分，并且列出得到这个分数的过程。分析分析我们在这条“线”当中继续删边，并且每次删边都使被删边两旁的点按边上的操作符合并，图五。这样进行了n-1次删边操作后，“线”变成了一个点。我们的目的，就是安排删边的顺序，使最后的点上的数尽可能的大。拿到题目之后，我们马上可以想到用枚举法——枚举删边的先后顺序。但边数最大可以达到50，枚举的复杂将会有50！。因此枚举算法马上被排除了。对最优化问题的求解，我们往往可以使用动态规划来解决。这道题是不是可以使用动态规划呢？我们先对题目进行一些变化——原题中顶点上的数可以为负数，现在我们规定这个数一定大于等于0；原题中边可以为乘号，现在我们规定只能为加号。题意改变后，我们想到了什么？对！“石子合并”。动态规划我们先枚举第一次删掉的边，然后再对每种状态进行动态规划求最大值用f(I,j)表示从j开始，进行i次删边操作所能得到的最大值，num(i)表示第i个顶点上的数，那么：)(),1()),(),((max),(11inumifkikjfikfjifik进一步分析现在我们来考虑加入乘号后的情况。由于所有的顶点上的数都为非负数，因此即使有了乘法，函数f的无后效性并不被破坏。我们可以在前一方程的基础上进行改进：（opr(i)表示第i条边上的操作符）)(),1(),,,(max),(11inumifkikjikactjifiky2)f(x2,*y1)f(x1,-1)-opr(x2y2)f(x2,y1)f(x1,1)-opr(x2)2,2,1,1(时，当时，当yxyxAct进一步分析最后，我们允许顶点上出现负数。以前的方程还适不适用呢？这个例子的最优解应该是（3+2）*（-9）*（-5）=250，然而如果沿用以前的方程，得出的解将是（（-10）*3+2）*（-5）=140。为什么？我们发现，两个负数的积为正数；这两个负数越小，它们的积越大。我们从前的方程，只是尽量使得局部解最大，而从来没有想过负数的积为正数这个问题。-932-5**图六+最终？我们引入函数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)=*时，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（先要枚举每一条边，然后再用复杂度为n3的动态规划解决）。能量项链在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是Mars人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头标记为r，尾标记为n，则聚合后释放的能量为（Mars单位），新产生的珠子的头标记为m，尾标记为n。需要时，Mars人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。例如：设N=4，4颗珠子的头标记与尾标记依次为(2，3)(3，5)(5，10)(10，2)。我们用记号⊕表示两颗珠子的聚合操作，(j⊕k)表示第j，k两颗珠子聚合后所释放的能量。则第4、1两颗珠子聚合后释放的能量为：(4⊕1)=10*2*3=60。这一串项链可以得到最优值的一个聚合顺序所释放的总能量为((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710。【输入文件】输入文件energy.in的第一行是一个正整数N（4≤N≤100），表示项链上珠子的个数。第二行是N个用空格隔开的正整数，所有的数均不超过1000。第i个数为第i颗珠子的头标记（1≤i≤N），当i时，第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。第N颗珠子的尾标记应该等于第1颗珠子的头标记。至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。【输出文件】输出文件energy.out只有一行，是一个正整数E（E≤2.1*10^9），为一个最优聚合顺序所释放的总能量。分析先枚举一个位置p，将珠子变成一条链。设链中的第i颗珠子头尾标记为(Si-1与Si)。令G[i,j]表示从第i颗珠子一直合并到第j颗珠子所能产生的最大能量，则：G[i,j]=min{G[i,k]+G[k+1,j]+Si-1*Sk*Sj,i=kj}边界条件：G[i,i]=0最后的最优解为G[1,n]该算法需要枚举p,i,j,k，而且每一重枚举都是O(n)，所以总的时间复杂度为O(n4)，而n可能有100，因此直接实现这个算法有超时的危险。在上式中，我们的方程只和珠子的标记(即Si)有关，而与编号无关，因此，珠子从1到n编号和2到n+1编号是等效的。现在不枚举p，令Si=Simodn(n=i=2n)，仍用上面的方程计算，则计算所得的G[1,n]为从第一颗珠子前断开时最优值，而G[2,n+1]计算的正好是从第二颗珠子前断开时的最优值。G[i,n+i-1]表示从第i颗前断的最优值。利用这种方法将长为n的环变为了长为2n的链，却能不能枚举p而算得最优值。一般而言，如果是对环的最优值问题能通过枚举断点而求得最优解，都可以将环拉成链后复制一遍，求出链中所有长为n的段的最优值，此值即为环中对应的最优解。这此对环的动态规划最简单也是最常用的降维方法。通过拉伸后，复杂度降为了O(n3)，可以迅速出解。BlocksJimmy最近迷上了一款叫做方块消除的游戏.游戏规则如下：n个带颜色方格排成一列，相同颜色的方块连成一个区域（如果两个相邻的方块颜色相同，则这两个方块属于同一个区域).游戏时，你可以任选一个区域消去.设这个区域包含的方块数为x,则将得到x^2的分值.方块消去之后，右边的方格将向左移动.虽然游戏很简单，但是要得到高分也不是很容易.Jimmy希望你帮助他找出最高可以得到多少分N200.Sample如图，依次消去灰,白,黑区域，你将得到4^2+3^2+2^2=29分，这是最高得分.算法分析合并颜色序列，如11133244455根据方块消除的规则，连在一起的相同颜色方块可以合并上面的颜色序列为(1,3),(3,2),(2,1),(4,3),(5,2),其中(a,b)表示有b个颜色为a的连在一起.于是题目可以表示成color[i],len[i],1=i=m,m表示颜色序列总共有m段.上面的颜色序列中,m=5,color[1..5]=(1,3,2,4,5)len[1..5]=(3,2,1,3,2)定义状态设S(i,j,k)为(color[i],len[i]),(color[i+1],len[i+1])…(color[j-1],len[j-1])的连续同色整段以及在一系列消除操作后j后接了k个颜色为color[j]的方块(color[j],len[j]+k)的一个颜色序列.设f(i,j,k)表示消除S(i,j,k)这一个颜色序列可以得到的最大分值.算法分析算法分析动态规划转移如果立刻将(color[j],len[j]+k)这一段消除，则转移为f(i,j-1,0)+(le