Detail of message

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

证明贪心错误

Posted by bellxtq at 2013-10-23 14:53:34 on Problem 1260
In Reply To:为什么我这样推不对呢? Posted by:sysu_wwl at 2008-11-18 20:47:34

价格pa<pb<pc
假设贪心得出(a+10)pa>a*pb和(a+b+10)pb>(a+b)*pc两个前提
但是对于(a+10)*pa+(b+c+10)*pc<(a+b+c+10)*pc即不采取归并更小的情况是否存在呢
化简式子：
(a+10)*pa<(a+b)*pc

对比条件，我们知道(a+10)*pa>a*pb和(a+b+10)pb>(a+b)*pc

完全可以有a*pb<(a+10)*pa<(a+b)*pc<(a+b+10)*pb

所以贪心策略是错的

Followed by:

打错了，(a+10)*pa<a*pc是成立的 (0) bellxtq 2013-10-23 14:58:17

Post your reply here:

Home Page Go Back To top