# | User | Rating |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3821 |
3 | Benq | 3736 |
4 | Radewoosh | 3631 |
5 | jqdai0815 | 3620 |
6 | orzdevinwang | 3529 |
7 | ecnerwala | 3446 |
8 | Um_nik | 3396 |
9 | ksun48 | 3388 |
10 | gamegame | 3386 |
# | User | Contrib. |
---|---|---|
1 | cry | 164 |
1 | maomao90 | 164 |
3 | Um_nik | 163 |
4 | atcoder_official | 161 |
5 | -is-this-fft- | 158 |
6 | awoo | 157 |
7 | adamant | 156 |
8 | TheScrasse | 154 |
8 | nor | 154 |
10 | Dominater069 | 153 |
Name |
---|
It is basically a Dynamic Programming solution.
This is my Accepted C++14 brute-force recursive solution, which may be more intuitive and simpler to comprehend.
Can you elaborate your solution
The idea is to store the present state in a
state_t
object that consists of the triple:cookies: the present number of cookies
S: the present number of cookies gained per second
T: the present time in seconds
The initial state is (0, S, 0), and C is the number of desired cookies.
A factory is storied as a
factory_t
object that consists of the triple:cost: the cost of purchasing the factory
production: the number of bonus cookies it produces when purchased
bought: a boolean flag that indicates whether it has been bought or not
Initially, all the N factories are not bought.
The recursive
factories_t::min_time( state_t x )
function is a brute-force recursive function that initializesmin_time
to the minimum number of seconds required so that the number of cookies reaches at least C according to the number of cookies and the gain per second in the present state without purchasing more factories.Then, the function iterates on all factories. If some
factory[ i ]
is not bought yet, then its correspondingdelta
is computed, which is the minimum time according to the present state such that it is possible to buy such factory. If such number is strictly positive, then the time the present state advanced by that duration. Then, the present state is updated according as the factory is purchased and the factory is marked as bought. The same function is then called recursively with the updated state to compute the minimum time for the update state.After returning back from the recursive call,
min_time
is updated, and the state is backtracked to its previous state so as to check if it is possible to update the minimum time to a lower value by buying another factory at that recursion level.