subject
Mathematics, 19.05.2021 18:30 chloelandry

In this game, there is a stack of n bricks. The ith brick in the stack is worth v[i] points (where v[0] is the value of the top brick). The players take turns removing either 1, 2, 3 or 4 bricks from the top of the stack. The player that removes a brick earns the number of points associated with the brick. The game ends when all the bricks have been removed, and the winner is the player who has earned the most points. For example, if v = [1, 1, 3, 4] and Smoov is the first player to move, then Smoov's optimal strategy is to take just the first brick (earning 1 point). Curly's optimal strategy is then to take the next two bricks (earning 4 points). Smoov then finishes by taking the last brick (earning 4 more points). Therefore, the maximum score Smoov can earn is 5. Assume that Smoov takes the first turn and that both Smoov and Curly play optimally. Given the list v of the values of the bricks (all integers greaterthanorequalto 0), output the maximum score Smoov can earn. (a) Define the subproblems to be solved in English. Solution: Let s_i denote the optimum score for whoever's turn it is when v_i is the top remaining brick. The subproblems are to compute s_i for each i from n - 1 to 0. (b) Define an appropriate recurrence for the subproblems. Solution: s_i = {0, i greaterthanorequalto n v[i] + max (min(s_i+2, s_i+3), v[i + 1] + min(s_i+3, s_i+4)), i < n For the particular input v = [1, 2, 0, 8, 0, 3, 3, 2], compute s_i for 0 lessthanorequalto i lessthanorequalto 7.

ansver
Answers: 3

Another question on Mathematics

question
Mathematics, 21.06.2019 15:20
Compare the subtraction problems 6/8 - 5/8 = 1/8 and 6/9 - 7/9 = 1/9 why is the answer to the first problem positive and the answer to the second problem negative
Answers: 1
question
Mathematics, 21.06.2019 20:00
Abcd is a square. what is the measure of angle bac
Answers: 2
question
Mathematics, 21.06.2019 21:30
*let m∠cob = 50°30’, m∠aob = 70° and m∠aoc = 20°30’. could point c be in the interior of ∠aob? why? a. point c could be the interior of aob but it is not the only case b. point c is the interior of aob c. point c is not the interior of aob d. the given is not possible for the plane geometry answer
Answers: 1
question
Mathematics, 21.06.2019 21:30
High school seniors with strong academic records apply to the nation’s most selective colleges in greater numbers each year. because the number of slots remains relatively stable, some colleges reject more early applicants. suppose that for a recent admissions class, an ivy league college received 2851 applications for early admission. of this group, it admitted 1033 students early, rejected 854 outright, and deferred 964 to the regular admission pool for further consideration. in the past, this school has admitted 18% of the deferred early admission applicants during the regular admission process. counting the students admitted early and the students admitted during the regular admission process, the total class size was 2375. let e, r, and d represent the events that a student who applies for early admission is admitted early, rejected outright, or deferred to the regular admissions pool.suppose a student applies for early admission. what is the probability that the student will be admitted for early admission or be deferred and later admitted during the regular admission process?
Answers: 3
You know the right answer?
In this game, there is a stack of n bricks. The ith brick in the stack is worth v[i] points (where v...
Questions
question
Mathematics, 25.11.2020 14:00
question
Biology, 25.11.2020 14:00
question
English, 25.11.2020 14:00
question
Mathematics, 25.11.2020 14:00
question
Mathematics, 25.11.2020 14:00
question
Mathematics, 25.11.2020 14:00
Questions on the website: 13722361