国家集训队2005论文集 杨弋

《国家集训队2005论文集 杨弋》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、从《小H的小屋》的解法谈算法的优化安徽师范大学附属中学杨弋题目大意小H有一个院子，东西方向长为100单位。东墙和西墙均平行于y轴，北墙和南墙分别是斜率为k1和k2的直线。北墙和南墙分别围有多块草坪，每块草坪都是一个矩形，矩形的每条边都平行于坐标轴。相邻两块草坪的接触点恰好在墙上，接触点的横坐标被称为它所在墙的“分点”，这些分点必须是1到99的整数。北墙要有m块草坪，南墙要有n块草坪，并约定，m≤n。如果记北墙和南墙的分点集合分别为X1,X2，则应满足X1X2。输入k1，k2，m，n。k1和k2为正实数，m和n为正整数，且2≤m≤n≤100。假定南北墙距离很远，南墙草坪

2、和北墙草坪不会重叠。题目大意让我们来看一个例子：输入：0.50.224图中给出的就是这组数据的最优解，最小面积为3000。yx西东南北0255075100算法一看到题目，我们首先想到的算法是动态规划。我们用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,计

3、算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……kf(w,u,v)kakkb时曲线是上升的kb算法二我们枚举x，当x增大的时候，ka不会减小。这样，我们可以枚举x的同时计算ka。由于x和ka都是递增的,该算法的时间复杂度降为O(l2mn)，空间复杂度仍然是O(ln)。算法二我们注意到计算f(w,u,v)的最优

4、解所用的x,k必不小于计算f(w,u+1,v)的最优解所用的x,k（假如f(w,u+1,v)存在的话），所以我们可以记录计算最优解时用的x,k，从而进一步减少程序运行所用时间。算法二无论在时间复杂度上还是在空间复杂度上都足够应付这道题目的所有数据了。那么，究竟有没有更好的方法呢？算法三现在让我们彻底抛弃动态规划的思想，来试一试贪心算法在此题中的应用。100Hil5050252550北墙草坪南墙草坪k1=k2=1,m=2,n=3我们尽可能平均地分配北墙草坪的长度然后再尽可能平均地为南墙草坪分配长度S=87505050252550算法三100Hil5743292843北

5、墙草坪南墙草坪k1=k2=1,m=2,n=3但是……S=8572这样的贪心算法是错误的!算法三为什么说这个贪心算法是错误的？因为每一块北墙草坪对应的南墙草坪数量并不是相等的！如果我们能使每一块北墙草坪对应的南墙草坪数量相等……显然，这时尽量平均分配得到的就是最优解了北墙草坪南墙草坪算法三现在我们假设最优解有这样的情况北墙草坪对应的南墙草坪块数的差距大于1了。算法三那么……总存在这样的调整，调整以后差距会小于等于1，并且总面积不会比原来大。我们可以把南墙草坪按块数尽可能平均地分配给北墙草坪！算法三这里是一个例子我们有3块北墙草坪和10块南墙草坪，该怎么分配呢？算法三我们

6、先把整个墙分成两部分，第一部分包含m1段北墙草坪，每段对应n1段南墙草坪；第二部分包含m2段北墙草坪，每段对应n2段南墙草坪。如果两部分的长度确定了，在两部分内，都可以直接贪心求该部分的最小面积。我们枚举其中一个部分的长度，另一个部分的总长度也就确定了，此时的最优解可以在O(1)时间内计算出来。于是，我们得到了一个全新的算法：算法三就像这样：这样，整个算法的时间复杂度是O(l-n)的，空间复杂度是O(1)的。算法四我们的优化还没有结束！现在让我们来看看算法四吧我们设分给第一部分的东西向长度为i。设能使S取到最优解的最小i为i1，能使S取到最优解的最大i为i2。和我们在

7、思考算法二时的情况类似，我们发现ii2时S随i增大而增大，在i1≤i≤i2时S始终能取到最小值。算法四就像这样iSi1i