文档介绍：合并类动态规划
长沙市雅礼中学朱全民
合并类动态规划的特点
合并:意思就是将两个或多个部分进行整合,当然也可以反过来,也就是是将一个问题进行分解成两个或多个部分。
特征:能将问题分解成为两两合并的形式
求解:对整个问题设最优值,枚举合并点,将问题分解成为左右两个部分,最后将左右两个部分的最优值进行合并得到原问题的最优值。有点类似分治算法的解题思想。
典型试题:整数划分(见动归2),凸多边形划分(见动归3)、石子合并、多边形合并、能量项链等。
能量项链
在Mars星球上,每个Mars人都随身佩带着一串能量项链。
在项链上有N颗能量珠。
能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。
对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。如果前一颗能量珠的头标记为m,尾标记为r,后一颗能量珠的头标记为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颗珠子一直合并到第j颗珠子所能产生的最大能量,则有:
F(i,j)=Max{F(i,k)+F(k+1,j)+Si-1*Sk*Sj, i<=k<j}
边界条件:F(i,i)=0
1<=i<k<j<=n
至于圈的处理,与石子合并方法完全相同,时间复杂度O(8n3) 。
思考题1:整数划分
给出一个长度为n的数
要在其中加m-1个乘号,分成m段
这m段的乘积之和最大
m<n<=20
有T组数据,T<=10000
贪心法
尽可能平均分配各段,这样最终的数值将会尽可能大。但有反例。如191919分成3段
19*19*19=6859
但191*91*9=156429,显然乘积更大。
将一个数分成若干段乘积后比该数小,因为输入数不超过20位,因此不需高精度运算。
证明:
假设AB分成A和B,且A,B<10,则有
AB=10*A+B>A*B(相当于B个A相加)
同理可证明A,B为任意位也成立
动态规划
可以先预处理出原数第i到j段的数值A[i,j]是多少,这样转移就方便了,预处理也要尽量降低复杂度。
F[i,j]表示把这个数前i位分成j段得到的最大乘积。
F[i,j]=F[k,j-1]*A[k+1,i],
1<k<i<=n, j<=m
时间复杂度为O[mn2]
由于有10000组数据,因此估计时间复杂度为10000*203=8*107
至于说输出,记录转移的父亲就可以了。
思考题2:凸多边形的三角剖分
给定由N顶点组成的凸多边形
每个顶点具有权值
将凸N边形剖分成N-2个三角形
求N-2个三角形顶点权值乘积之和最小?
样例
上述凸五边形分成△123 , △135, △345
三角形顶点权值乘积之和为:
121*122*123+121*123*231+123*245*231= 12214884