Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

此题使用贪心算法正确性的证明

Posted by njuallen at 2015-05-31 13:12:11 on Problem 1083
关于这个算法的正确性的证明:
首先,我们可以看到好多人的解决方法是给每个路径都加上一个计数器,最后这么多计数器的最大值就是结果,但计数器的最大值只是结果的下限,我们还必须说明存在一个解能达到这个下限,这个解必然就是最优解了。
为了证明这个贪心算法正确,我们可以证明:在计数器的最大值为N时,经过一轮贪心选互不相交区间操作之后,计数器的最大值为N-1。
1、所有在这一轮被选走的区间(即在这一轮移动玩的桌子)上的计数器的值必然减1。
2、其他区间上的计数器值不变,但其他区间上的计数器的值一定小于N。
假设第一轮移走的连续两个桌子占用走廊区间为[a1,a2],[b1,b2],我们要证明区间(a2,b1)上的所有计数器的值全部都小于N,不妨考察a2+1处的计数器值。
假设a2+1处的计数器值为N,则由于搬桌子时采取了贪心策略,且搬完桌子[a1,a2]之后,直接搬走了桌子[b1,b2],所有覆盖了a2+1的桌子并未被移动,因此覆盖a2+1处的N个桌子的区间的开始位置必然小于a2,即覆盖了a2+1的N张桌子必然同时覆盖a2。同时考虑到a2处已经被搬走了一张桌子,因此在这次搬桌子之前,a2处计数器的值为N+1,与假设矛盾!因此a2+1处的计数器的值必然小于N,同理,(a2,b1)区间上的所有计数器的值全都小于N。
证明完成!
搬了一轮桌子后,计数器最大值就必然减1,因此最多搬N次桌子,所有计数器值为0,即搬完了。
同时,由于计数器最大值为N,意味着我们至少要搬N次,所以用此贪心算法达到的搬N次是最优结果。
亦即次贪心算法正确!
证明完成!

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator