Блог пользователя mufasa

CBR #82(div 2) problem C
Автор mufasa, 13 лет назад, По-английски
Can anybody suggest me optimal substructure for the above problem.
  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
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.
→ Ответить