Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
贪心证明首先假设有a、b两头牛,当先选a时,损失为2*Ta*Db,反之,损失为2*Tb*Da,同时除以Da*Db,可以得到,破坏力衡量指标T/D。 假设有a1、a2、....、an头牛,且牛的破坏力为a1>a2>a3>....>an,我们假设优先选择破坏力大的牛是一个最优解,当存在一个最优解为ak1,ak2,ak3...akn时,容易知道,当牵走aki和aki+1两头牛时,所花费时间相同,即其他牛所产生的总破坏力相同,如果aki的破坏力<aki+1,我们可以调换两者的顺序,从而得到另一个最优解,接着这个最优解,进一步重复上述过程,从而可以证明优先选择破坏力大的牛是一个最优解 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator