mufasa's blog

CBR #82(div 2) problem C
By mufasa, 13 years ago, In English
Can anybody suggest me optimal substructure for the above problem.
  • Vote: I like it
  • 0
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Suggest that stuffing types are ordered from 0 to N (we also consider empty stuffing as a special kind of stuffing indexed zero).
Now, you can ask the question: What is the maximal amount of money you can earn if you have REST grams of dough and use stuffing types beginning from index INDEX to index N.

Let F(rest, index) be the function that can answer this question. How can it be calculated? 

We can make count buns with IND stuffing where . 
So, F(REST, IND) is equal to
 max{d[IND] * count + F(REST - c[IND] * count, IND + 1)}, where  count = 0, ...MIN. 

F(REST, IND) = 0, if REST ≤ 0 or IND > N.
→ Reply