USACO S1.3 Barn Repair 贪心证明

证明1：用M个板子所得的最小长度不会比用K（$ 1<=K<M\()个板子所得的最小长度大（在非空畜栏数量大于可购买的最多的板子数量时） 若在用K个板子所得最优解中，存在至少覆盖一个空的畜栏的某一个板子，将板子分开，空过空的畜栏，显然最优解会更小。 若在用K个板子所得最优解中,不存在一个板子覆盖住至少一个空的畜栏，我们将任意一个板子分成两段，最优解不变。 综上所述，在非空畜栏数量大于可购买的最多的板子数量时，用M个板子所得的最小长度不会比用K（\) 1<=K<M\()个板子所得的最小长度大。 以下证明均在非空畜栏数量大于可购买的最多的板子数量情况下。 我们将非空兽栏称作点，其他区域为空白。 此题可以简化为用M条线段，覆盖所有的点，且使得线段总长最小。 等价于在两个点间任意位置放置挡板（注意每两个点间最多放一个），需要放置M-1个，使得线段总长最小。 注意这里算距离不是挡板到挡板之间，挡板仅仅用来启发思路，而是与挡板最接近的点开始算 一个例子： @。。。。。。。。。。。。。。@@ 1................................................k k+1 3个点，2个线段，需放置一个挡板到点1和点k之间，算长度的时候第二段以点k开始，第一段以点1结束。 设两点差值:\)i=p_{i+1}-p_i (1<=i<c)$ 设i的序列A={\(j_1,j_2,j_3,...,j_c\)},且A以非递增顺序排列。 贪心规则：每次选择A未被选择的最大的差值 证明归纳基础：最优解中包含选择1 任取最优解D,D中的选择以不递减排列且第一个选择不为A中第一个。 设其第一个选择为k,替换k为A中第一个选择生成D’. 总长度LD’=LD+k-1-(\(j_1\)-1) =LD+k-\(j_1\) 因为\(k<=j_1\) 所以LD’<=LD,LD’也为最优解且包含\(j_1\) 证明归纳步骤 假设前k步选择导致最优解 设最优选择序列D={\(i_1,i_2,i_3,...,i_k\)}\(\cup\)B; 根据归纳基础，存在子问题中的最优解B’包含子问题中最大的差值，设其为\(i_{k+1}\) D={\(i_1,i_2,i_3,...,i_k\)}\(\cup\)B={\(i_1,i_2,i_3,...,i_k,i_k+1\)}\(\cup\)(B’-\(i_{k+1}\)) 所以前k+1个选择也能导致最优。 证毕。