USACO/barn1

详细解析

术语：状态S(i) 状态S(i)是指在牛棚(stall)上放置ｉ个木板(block)后使得所有有牛儿居住的stall均被覆盖时所得到的状态。 由此可知这种状态可能不止一个。

术语：|S(i)| |S(i)|表示状态S(i)所覆盖的牛棚(stall)的总数，也就是木板(block)的长度

术语：状态是最优的 说一个状态S(i)是最优的，当且仅当不存在S'(i)使得|S'(i)| < |S(i)| 最优的状态也可能有多个。

术语：空白（blank） 空白(blank)指一段连续的没有牛儿居住的牛棚，我们只考虑两边不能在增加的空白，即左、右两边要么有牛居住，要么没有牛棚。

术语：|空白（blank）| |k|指空白k的长度

术语：增加block过程 增加block过程就是在一个状态上找出一段被覆盖的空白，把覆盖这个空白的木板挖去空白所对应的位置，即一个木板变为两个，被覆盖的空白少了一个。 在状态为S(i)时调用此过程后状态变为S(i+1)。

此题的算法是这样的，首先用一块木板从第一个牛的位置覆盖到最后一个牛的位置。 然后反复调用“增加block过程”，直到所使用的木板数达到题目给出的限制，或空白全部被填满。 这样得到的状态S(ｐ)就是最优状态。［ｐ等于给出的可用木板数与空白数的较小值］

这个一个贪心算法，下面使用一个循环不变式证明它的正确性，这里假设没有两个空白具有相同的长度(因为当最长的空白有多个时可以选择任意一个，所以这种假设是可行的)。 循环不变式：在首先用一块木板从第一个牛的位置覆盖到最后一个牛的位置后(得到状态S(1))，每次调用“增加block过程”后得到的状态S(ｉ)均是最优的。 初始：容易看出S(1)是最优的。 中间：假设S(k)是最优的，则使用“增加block过程”后S(k+1)也是最优的，下面用反证法来证明。 如果S(k+1)不是最优的，则存在S'(k+1)最优，使得 |S'(k+1)| < |S(k+1)|，且S'(k+1)不等于S(k+1) 设在S(k)到S(k+1)的转变中我们去掉的那个最长的空白为b,则有 |S(k+1)| = |S(k)| - |b|， 又因为|S'(k+1)| < |S(k+1)|，所以有|S'(k+1)| <　|S(k)| - |b|，即　|S(k)|　> |S'(k+1)| + |b|　＜１式＞， 当S'(k+1)没有覆盖ｂ时，我们可以把ｂ两头的木板连起来覆盖ｂ得到S'(k),且有 |S'(k)| = |S'(k+1)| + |b|， 根据＜１式＞有 |S(k)| > |S'(k)|　，这与假设S(k)最优矛盾。 当S'(k+1)覆盖了ｂ时，因为ｂ是S(k)中最长的空白，则S'(k+1)中一定存在一个没有覆盖的空白d,使得 |d| < |b|， 这是因为如果ｄ不存在的话表明前ｋ次删除空白时我们删除了最长的ｋ个空白(b是第ｋ长的)，这意味着S'(k+1)等于S(k+1)，别忘了我们假设没有两个空白具有相同的长度。 因此S'(k+1)覆盖了ｂ时ｄ一定存在，此时如果在S'(k+1)中交换ｂ、ｄ（不覆盖ｂ，而覆盖ｄ），则可得S(k+1)， 又因为 |d| < |b| ，所以 |S(k+1)| < |S'(k+1)|，这与S'(k+1)最优矛盾。

由此可知S(k+1)是最优的，即算法正确。

原文见: http://sdjl.me/?p=40

思路一

要使木板总长度最少，就要使未盖木板的长度最大。

我们先用一块木板盖住牛棚，然后，每次从盖住的范围内选一个最大的空隙，以空隙为界将木板分成两块，重复直到分成m块或没有空隙。

可以用二叉堆来优化算法。

贪心的证明略。

思路二

显然，当所有木板均用上时，长度最短（证明....）。 正向思维，初始状态有c块木板，每块木板只盖住一个牛棚。

由c块倒推至m块木板，每次寻找这样的两个牛棚：其间距在所有未连接的木板中最小。 当这两个牛棚的木板连接时，总木板数减1，总长度增加最小

思路三

还可以用动态规划求解,将所有牛的牛棚序号a[]排序后,设f[i,j]表示用前i个木板修到第j头牛所用的最短长度.

 f[i,j]=min{f[i-1,j-1]+1,f[i,j-1]+a[j]-a[j-1]}  

f[i-1][j-1]+1表示在第j个牛棚使用一块新的木板（长度为1）覆盖， f[i][j-1]+a[j]-a[j-1]表示延长第i块木板至第j个牛棚。

思路四

显然，当所有木板均用上时，长度最短。用上m块木板时有m-1各间隙。现在的目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序，选取最大的m-1个作为间隙，其余地方用木板盖住即可。

参考代码

C

C++

Pascal

Java

引用

[1]