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 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:

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