文档介绍：从《小H的小屋》的解法谈算法的优化
安徽师范大学附属中学杨弋
题目大意
小H有一个院子,东西方向长为100单位。东墙和西墙均平行于y轴,北墙和南墙分别是斜率为k1和k2的直线。北墙和南墙分别围有多块草坪,每块草坪都是一个矩形,矩形的每条边都平行于坐标轴。相邻两块草坪的接触点恰好在墙上,接触点的横坐标被称为它所在墙的“分点”,这些分点必须是1到99的整数。北墙要有m块草坪,南墙要有n块草坪,并约定,m≤n。如果记北墙和南墙的分点集合分别为X1,X2,则应满足X1 X2。
输入k1,k2,m,n。k1和k2为正实数,m和n为正整数,且2≤m≤n≤100。
假定南北墙距离很远,南墙草坪和北墙草坪不会重叠。
题目大意
让我们来看一个例子:
输入: 2 4
图中给出的就是这组数据的最优解,最小面积为3000。
y
x
西
东
南
北
0
25
50
75
100
算法一
看到题目,我们首先想到的算法是动态规划。
我们用f(w,u,v)表示长度为w,北墙u块草坪和南墙v块草坪时的最小面积。
令一块北墙草坪和其对应的南墙草坪为一个“块”,若北墙草坪长度为x,南墙草坪块数为k,则该块最小面积为area(x,k)。
f(w,u,v) =min{f(w-x,u-1,v-k)+area(x,k) }
x
共k块
……
……
算法一
这样,我们就得到了算法一:
1、枚举所有合法的w,u,v,对于每一组w,u,v,计算f(w,u,v) 。
2、在计算f(w,u,v)时,枚举所有合法的x,k,从而求出f(w,u,v) 。
3、 f(100,m,n)就是我们所要求的解。
该算法时间复杂度是O(l2mn2)
空间复杂度是O(ln)
太慢了!
算法一
看来,我们必须优化我们的算法……
算法二
在状态转移时,假如我们已经确定了x……
k
f(w,u,v)
ka
k<ka时曲线是下降的
k>kb时曲线是上升的
kb
算法二
我们枚举x,当x增大的时候,ka不会减小。
这样,我们可以枚举x的同时计算ka 。
由于x和ka都是递增的,该算法的时间复杂度降为O(l2mn),空间复杂度仍然是O(ln)。
算法二
我们注意到计算f(w,u,v)的最优解所用的x,k必不小于计算f(w,u+1,v)的最优解所用的x,k (假如f(w,u+1,v)存在的话),所以我们可以记录计算最优解时用的x,k,从而进一步减少程序运行所用时间。
算法二无论在时间复杂度上还是在空间复杂度上都足够应付这道题目的所有数据了。
那么,究竟有没有更好的方法呢?