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 |
https://mail.cs.pub.ro/~mugurel.andreica/task_archive/USA%20-%20Olympiads%20&%20Contests/USACOs/USACO%202003-2004/Fall%20Contest/Green%20Division/problem_analysis.htmThis is a relatively standard Dynamic Programming problem. The key is to maintain the optimal funness that can be obtained for any particular smartness (in an array). It is important to also do this for negative smartness, since another cow could be added to make the smartness positive later. Start with no cows. It is impossible to make any non-zero smartness, and for zero smartness the optimal funness is zero. Now start adding cows one at a time. For each original smartness/funness combination, try adding this cow. This produces a new S/F combination. If this particular smartness has never been produced, or has been produced but with less funness, then overwrite the array entry with the new funness amount. Once you have added all the cows, check all the array entries for non-negative smartness and funness, and pick the one with the highest total. Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator