Can anybody suggest me optimal substructure for the above problem.
# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3831 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | gamegame | 3386 |
10 | ksun48 | 3373 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 160 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
_jte_
|
13 years ago,
#
|
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.
→
Reply
|
Name |
---|