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

https://mail.cs.pub.ro/~mugurel.andreica/task_archive/USA%20-%20Olympiads%20&%20Contests/USACOs/USACO%202003-2004/Fall%20Contest/Green%20Division/problem_analysis.htm

Posted by hehexiaobai at 2011-05-02 22:16:23 on Problem 2184 and last updated at 2011-05-11 19:39:08
This 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:
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