VAMPIER's blog

Ask about ( 757 — Gone Fishing ) uva problem
By VAMPIER, history, 9 years ago, In English

if there is anyone solve this problem please comment with the link of solution https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=698

  • Vote: I like it
  • -8
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
9 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

It can be solved with DP.

  • First of all, let's divide everything by 5 to make things simpler.
  • Let DP[i][t] be the maximum amount of fish we can catch if we start at lake i and have t minutes left. It's easier done with recursive DP with memoization, trying to stay as much as possible at each lake. To reconstruct the answer, along with the DP value, store the amount of time spent to achieve the best answer.
  • Finally, reconstruct the answer and remember to multiply values by 5.
→ Reply