文档介绍：区间类动态规划
长沙市雅礼中学朱全民
1
整数划分
给出一个长度为n的数
要在其中加m-1个乘号,分成m段
这m段的乘积之和最大
m<n<=20
有T组数据,T<=10000
2
贪心法
尽可能平均分配各段,这样最终的数值将会尽可能大。但有反例。如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为任意位也成立
3
动态规划
可以先预处理出原数第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[m2n]
由于有10000组数据,因此估计时间复杂度为10000*203=8*107
至于说输出,记录转移的父亲就可以了。
4
石子合并
在一园形操场四周摆放N堆石子(N≤100);
现要将石子有次序地合并成一堆;
规定每次只能选相临的两堆合并成一堆,并将新的一堆的石子数,记为该次合并的得分。
选择一种合并石子的方案,使得做N-1次合并,得分的总和最少
选择一种合并石子的方案,使得做N-1次合并,得分的总和最大
5
示例
6
贪心法
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
第三次13 5 4 2得分6
第四次13 5 6得分11
第五次 13 11得分24
第六次24
总分:61
显然,贪心法是错误的。
7
分析
假设只有2堆石子,显然只有1种合并方案
如果有3堆石子,则有2种合并方案,((1,2),3)和(1,(2,3))
如果有k堆石子呢?