NOI导刊区间类型动态规划

《NOI导刊区间类型动态规划》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、区间类动态规划长沙市雅礼中学朱全民整数划分给出一个长度为n的数要在其中加m-1个乘号，分成m段这m段的乘积之和最大mA*B(相当于B个A相加)同理可证明A,B为任意位也成立动态规划可以先预处理出原

2、数第i到j段的数值A[i,j]是多少，这样转移就方便了，预处理也要尽量降低复杂度。F[i，j]表示把这个数前i位分成j段得到的最大乘积。F[i,j]=F[k,j-1]*A[k+1,i],1

3、1次合并,得分的总和最少选择一种合并石子的方案,使得做N-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显然，贪心法是错误的。分析假设只有2堆石子，显然只有1种合并方案如果有3堆石子，则有2种合并方案，((1,2),3

4、)和(1,(2,3))如果有k堆石子呢？不管怎么合并，总之最后总会归结为2堆，如果我们把最后两堆分开，左边和右边无论怎么合并，都必须满足最优合并方案，整个问题才能得到最优解。如下图：动态规划设t[i,j]表示从第i堆到第j堆石子数总和。Fmax(i,j)表示将从第i堆石子合并到第j堆石子的最大的得分Fmin(i,j)表示将从第i堆石子合并到第j堆石子的最小的得分同理，Fmax[i,i]=0，Fmin[i,i]=0时间复杂度为O(n3)优化由于石子堆是一个圈，因此我们可以枚举分开的位置，首先将这个圈转化为链，因此总的时间复杂度为O(n4

5、)。这样显然很高，其实我们可以将这条链延长2倍，扩展成2n-1堆，其中第1堆与n+1堆完全相同，第i堆与n+i堆完全相同，这样我们只要对这2n堆动态规划后，枚举f(1,n),f(2,n+1),…,f(n,2n-1)取最优值即可即可。时间复杂度为O(8n3),如下图：能量项链在Mars星球上，每个Mars人都随身佩带着一串能量项链。在项链上有N颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。如果前一颗能量珠的头标记为m，尾标记为r，后一颗能量珠的头

6、标记为r，尾标记为n，则聚合后释放的能量为m×r×n（Mars单位），新产生的珠子的头标记为m，尾标记为n。显然，对于一串项链不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。分析样例：N=4，4颗珠子的头标记与尾标记依次为(2，3)(3，5)(5，10)(10，2)。我们用记号⊕表示两颗珠子的聚合操作，释放总能量：((4⊕1)⊕2)⊕3）=10*2*3+10*3*5+10*5*10=710动态规划该题与石子合并完全类似。设链中的第i颗珠子头尾标记为(Si-1与Si)。令F(i,j)表示从第i颗珠

7、子一直合并到第j颗珠子所能产生的最大能量，则有：F(i,j)=Max{F(i,k)+F(k+1,j)+Si-1*Sk*Sj,i<=k

8、析性质：一个凸多边形剖分一个三角形后，可以将凸多边形剖分成三个部分：一个三角形二个凸多边形（图2可以看成另一个凸多边形为0）动态规划如果我们按顺时针将顶点编号，则可以相邻两个顶点描述一个凸多边形。设f(i,j)表示i~j