基于动态与均分优化草坪布局设计报告.pdfVIP

《hut》设计报告

贝小辉

【题目背景】

本题是第二试的第二题，着重考察选手的基本功和对动态规划算法的优化能

力。

【题目分析】

由于题目中包含了很明显的最优子结构的性质，所以应该不难想到要用动态

规划来解决这个问题。

我们用f[l][m][n]表示长度为l（这里省略单位Hil，下同），北墙有m块草坪，

南墙有n块草坪时的最优解。如果北墙的最后一块草坪长度为x（这里的长度就

是指草坪在东西方向上的跨度），并且和这块草坪对应的南墙有k块草坪，那么

就有f[l][m][n]=f[l–x][m–1][n–k]+area[x][k]，其中area[x][k]表示北墙的一块

长度为x的草坪并且和这块草坪对应的南墙有k块草坪时的最小面积，由于北墙

22

的一块长度为x的草坪面积为k*x，南墙的一块长度为x的草坪面积为k*x，

12

根据均值不等式不难得出

22

xx

2

area[x][k](xmodk)*k2*+1+(k−xmodk)*k2*+k*x。而最后要

kk1



求的就是f[100][m][n]。

至此，我们已经得到了一个很简单的动态规划算法，但是经过分析，算法的

22

时间复杂度为O(lmn)，这对于题目中的要求l=100，m,n最大也为100显然是

无法承受的。我们还需对算法进行一些优化。

观察area数组的计算方式，不难发现它的关键就是均分。上，这也是解

决整个题目的思想，我们求最小面积的过程，实际上就是将草坪的长度尽量

均分的过程。如果我们把北墙的每块草坪和与之对应的南墙的草坪看作一个整体的

话，我们发现它们的顺序是可以任意调整的，这样我们按照北墙的草坪长度由小

到大的顺序将它们排序，对于北墙长度相等的情况，将它们按照南墙的草坪个数

由小到大排序，不难证明，排序后的北墙的草坪长度是逐渐递增的，每块北墙草

坪所对应的南墙草坪的块数也是逐渐递增的。

hutdesignreport

贝小辉

[Title

background]

Thisquestionisthesecondquestionofthesecondtest,focusingontestingthe

yersbasicskillsandoptimizationabilityofdynamicprogrammingalgorithms.

【Topicanalysis】

Sincetheque