设共有L快区域
证明：由贪心算法求的的这种种法的前i位（1=〈i〈=L）种树的棵数是任何一种可能的
种法中前i位种树棵数最少的种法；设这种种法的前i位种树棵数为Ai（1=〈i〈=L）
取任意一种不是贪心算法种法的可能种法，设它的前i位种树棵树为Bi（1=〈i〈=L）
等价证明
Ai〈=Bi（1=〈i〈=L）
当i=1时，若由贪心算法判断第一棵树可以去掉，A（1）=0〈=B（1）显然满足题设
若判断不可以去掉，说明任何一种种法的第一位都要种树，A（1）=B（1）=1，也满足题设
对i=1题设成立
若i=k时也成立，显然Ai〈=Bi（1=〈i〈=k）
当i=k+1时
当A（K）〈 B（K）时，
有A（K+1）〈=A（K）+1〈=B（K）〈=B（K+1）
考察A（K）= B（K）
当这种任意取的种法的第K+1位种树时，显然有A（K+1）〈=A（K）+1=B（K）+1=B（K+1）
若这一种种法的第K+1位不种树，
证明下面一种种法也是一种可能种法---即前K位是贪心算法的种法，后面N-K位为
这种第K+1位不种树的种法的后N-K位，C（i）=A（i）（i〈=k）；C（i）=B（i）
（L〉=i〉k）
证明任意居民的要求（m，n，t），这种新组合的种法都满足居民的要求
对于n〈=k，
因为在由贪心算法求的的种法中A（n）-A（m-1）〉=t所以新组合的种法中区间（
m，n）种树棵数也是A（n）-A（m-1）也就满足要求
对于m〉=k，则因为在第K+1位不种树的那种种法中B（n）-B（m-1）〉=t所以新组合的种法
中区间（m，n）种树棵数也是B（n）-B（m-1）也满足要求
对于m〈=k〈=n
因为新组合的种法中区间（m，n）种树棵数为A（K）-A（m-1）+B（N）-B（K）
而A（K）= B（K）
所以A（K）-A（m-1）+B（n）-B（K）=B（n）-A（m-1）〉=B（n）-B（m-1）
因为第K+1位不种树的那种种法为合乎要求的种法，所以B（n）-B（m-1）〉=t
由此知道新组合的种法也使（m,n）区间满足要求
所以综合区间的三种情况知道新组合的种法为合乎要求的种法
由此判定对于贪心算法第K+1棵树可以去掉
所以A（K+1）=A（K）=B（K）〈=B（K+1）
由归纳知道对任意i有A（i）〈=B（i）成立
当取i=L时，就说明贪心算法是最少的种树棵数的算法
------
我不是计算机系的当然也就不是ACM队的喽，只是喜欢数学和数据结构
不知道我这篇文章不是班门弄斧
gmail.com
|